Minimized Toll Fee

There are n countries in the world, connected by m bidirectional roads. Each road connects two countries and has an associated toll fee w_i. When a merchant travels along a road, he pays the toll fee. However, upon reaching his destination, the merchant is refunded an amount equal to the difference between the maximum toll fee and the minimum toll fee encountered along his path, i.e., \(\max w_i - \min w_i\). Therefore, if a merchant’s path has a total toll fee of \(S = \sum w_i\), his effective cost is

[ \text{Effective Cost} = S - (\max w_i - \min w_i)]

Now, there are k merchants starting from country 1, each traveling to a specified destination country to do business. Your task is to compute, for each merchant, the minimum possible effective toll fee from country 1 to his destination. If a destination is unreachable, output -1.

inputFormat

The first line contains three integers n, m, and k, representing the number of countries, the number of roads, and the number of queries (merchants), respectively.

The next m lines each contain three integers u, v, and w indicating that there is a bidirectional road between countries u and v with a toll fee of w.

The following k lines each contain an integer representing the destination country for a merchant.

outputFormat

Output k lines. For each query, output a single integer: the minimum effective toll fee from country 1 to the destination. If the destination is unreachable, output -1.

sample

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

3
4
7