We have a directed graph with n nodes and m edges. Edge i is from a_{i} to b_{i} with cost c_{i}. There are k special nodes in a graph, namely s_{1}, \cdots, s_{k}.

Call D(x, y) the minimum cost of a path from node x to node y. Calculate for every node i the value F(i) = \sum_{j = 1}^{k} D(i, s_{j}), that is, the sum of distances from that node to every special node.

It is guaranteed that every node is reachable from every other node.

Input

The first line contains the three integers n m k.

Then m lines follow. Every line contains the three integers a_{i} b_{i} c_{i}.

The last line contains the k integers s_{i}.

Output

Output n integers: the values F(i).

Constraints

• 1 \leq n \leq 1000
• n \leq m \leq 5 * 10^{5}
• 1 \leq k \leq 20
• 1 \leq c_{i} \leq 10^{9}
• 1 \leq a_{i}, b_{i} \leq n

Example

Input:

4 6 2
4 1 10
2 3 4
1 2 10
3 4 6
3 1 9
2 3 3
2 3 

Output:

23 3 19 43