In a beautiful campus, Panda and his friends are meeting for a meal. They enjoy spending time together on the way, as they can chat freely with each other.

The campus is modeled as a connected, undirected graph with $n$ nodes and $m$ edges with lengths. The meeting spot is the mall, which is located at node $1$. $k$ friends start from distinct nodes and travel to the mall. All friends move at the same speed ($1$ unit distance per unit time), and are allowed to change direction at any position along an edge (see the example explanation).

Let $t_{\text{meet}}$ be the earliest possible time such that all friends can reach the mall by that time. Based on this earliest possible meeting time, for each friend individually, find the maximum total time they can spend with company (meaning at least one other friend is at the exact same location on the graph, which could be a node or a position along an edge) before the final gathering at the mall.

When considering a specific friend $i$, the paths and movement strategies of all other friends $j \neq i$ are optimized to maximize the company time for friend $i$, as long as all friends arrive at the mall no later than $t_{\text{meet}}$.

Input

The first line contains an integer $T$ ($1 \le T \le 10^4$), denoting the number of test cases.

For each test case, the first line contains three integers $n, m, k$ ($2 \le n \le 3 \times 10^5$, $n - 1 \le m \le 10^6$, $2 \le k \le n$), representing the number of nodes, edges, and friends, respectively.

The second line contains $k$ distinct integers $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$), denoting the starting nodes of the friends.

The next $m$ lines each contain three integers $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$), indicating an edge between node $u$ and $v$ with length $w$. The graph is connected and has no duplicate edges or self-loops.

The sum of $n$ over all test cases does not exceed $3 \times 10^5$, and the sum of $m$ over all test cases does not exceed $10^6$.

Output

For each test case, output a line containing $k$ floating-point numbers separated by spaces, each formatted to exactly one decimal place, representing the maximum time with company for each friend.

Examples

Input 1

3
4 3 2
3 4
1 2 3
3 2 1
4 2 1
2 1 2
1 2
1 2 3
3 2 3
1 2 3
1 2 3
1 3 5

Output 1

3.0 3.0
1.5 1.5
3.5 3.5 2.5

Note

For the third test case in the example, the earliest meeting time at the mall is $5$ units of time.

• The friends from nodes $1$ and $2$ can meet midway on edge $(1, 2)$ in $1.5$ units, travel together back to the mall in another $1.5$ units, and then wait $2$ units at the mall, totaling $3.5$ units of companionship.
• The friend from node $3$ meets the friends from node $1$ midway on edge $(1, 3)$ in $2.5$ units and returns with them in $2.5$ units, totaling $2.5$ units of companionship.