Problem G: Hunting

Problem G: Hunting

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1379  Solved: 177
[Submit][Status][Web Board]

Description

Pisces likes hunting very much. There are \(n\) camps in the forest, with \(m\) directed weighted forest roads connecting them. Pisces would choose the path for hunting in accordance to his mood. The length of the path is the sum of the weight \(w\) of the roads he has passed. Note that he can pass any road for multiple times.

Now, Pisces wants to know the \(k\)-th minimum length of all the paths. There are \(q\) queries you need to answer.

Input

The first line contains an integer \(t\) \((1≤t≤100)\), which represents the number of the test cases.

The first line of each test case contains three positive integers \(n\), \(m\), \(q\) \((1≤n,m,q≤5*10^4)\).

Each of the next \(m\) lines contains \(3\) integers \(u\), \(v\), \(w\), indicating that there is a forest road from \(u\) to \(v\) and it weights \(w\) \((1≤u,v≤n,1≤w≤10^9)\).

Each of the next \(q\) lines contains one integer \(k\) \((1≤k≤5∗10^4)\) as mentioned above. It's guaranteed that \(Σn, Σm, Σq, Σmax(k)≤2.5∗10^5\) and \(max(k)\) won't exceed the number of paths in the forest.

Output

For each query, print one integer indicates the answer in line.

Sample Input

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

Sample Output

3
3

HINT

[Submit][Status]