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