Country J has $n$ cities, connected by $m$ one-way roads with known lengths.

Rainbow, who lives in Country J, has invited Vani to visit. However, as an experienced traveler, Vani is only interested in $k$ cities in Country J that are rich in history and have unique natural scenery.

To enhance the travel experience, Vani wants to know the minimum "all-pairs shortest path" among the cities he is interested in (i.e., the shortest distance between the closest pair of cities among those he is interested in).

Perhaps you have already guessed the rest of the story—Vani is busy sightseeing in other places these days, so please help him solve this problem.

Input

The input contains multiple test cases. The first line contains an integer $T$, representing the number of test cases. Note that each test case is independent.

For each test case, the first line contains three positive integers $n, m, k$, representing the $n$ cities in Country J (numbered $1$ to $n$), the $m$ roads, and the number of cities $k$ that Vani is interested in.

The next $m$ lines each contain three positive integers $x, y, z$, representing a one-way road from city $x$ to city $y$ with length $z$. Note that $x$ and $y$ may be equal, and a pair $(x, y)$ may appear multiple times.

The next line contains $k$ positive integers, representing the IDs of the cities Vani is interested in.

Output

For each test case, output a single integer representing the minimum shortest path between any two of the $k$ cities.

Examples

Input 1

2 
6 7 3
1 5 3
2 3 5
1 4 3
5 3 2
4 6 5
4 3 7
5 6 4
1 3 6
7 7 4
5 3 10
6 2 7
1 2 6
5 4 2
4 3 4
1 7 3
7 2 4
1 2 5 3

Output 1

5
6

Note

For the first test case, the shortest path from $1$ to $3$ is $5$; the shortest path from $1$ to $6$ is $7$; $3$ and $6$ are unreachable, so the closest pair is $1, 3$, and the minimum distance is $5$.

For the second test case, the shortest path from $1$ to $2$ is $6$; the shortest path from $5$ to $3$ is $6$; the other points are unreachable from each other, so the closest pairs are $1, 2$ and $5, 3$, and the minimum distance is $6$.

Constraints