12441244 SUSTech Online Judge
Problem 1244 --Hunting

## 1244: 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

[Submit][Status]