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.

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.

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