問題文

とある村には、$N$ 個の家と $M$ 個の電波塔があります。

家と電波塔のある地点には $1, 2, …, N + M$ の番号がつけられており、そのうち家は地点 $1, 2, …, N$ であり、電波塔は地点 $N + 1, N + 2, …, N + M$ です。

また、村には電線が $K$ 本あります。電線 $i \: (1 \leq i \leq K)$ は地点 $U_i$ と $V_i$ を双方向に結んでおり、時間 $T_i$ で電線間で通信を行うことができます。

ここで、$1 \leq i \leq N$ についてそれぞれ以下の問題を解いてください。

地点 $i$ について、電線をいくつか辿っていずれかの電波塔と通信するのに必要な最小の時間を求めてください。
ただし、どの電波塔とも通信が不可能な場合は $-1$ を出力してください。

制約

• $1 \leq N, M \leq 10^5$
• $1 \leq K \leq 10^5$
• $1 \leq U_i < V_i \leq N + M$
• $1 \leq T_i \leq 10^9$
• $i \neq j$ ならば、$(U_i, V_i) \neq (U_j, V_j)$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

出力

$1 \leq i \leq N$ についてそれぞれの問題の答えを改行区切りで出力せよ。

入出力例

4 3 5
1 2 4
1 4 2
2 5 6
2 6 8
4 7 3

5
6
-1
3

地点 $1$ について、地点 $1 → 4 → 7$ と辿ることによって $2 + 3 = 5$ の時間で電波塔との通信が可能です。
地点 $2$ について、地点 $2 → 5$ と辿ることによって $5$ の時間で電波塔との通信が可能です。
地点 $3$ については、いずれの電波塔とも通信を行うことができません。
地点 $4$ について、地点 $4 → 7$ と辿ることによって $3$ の時間で電波塔との通信が可能です。

8 5 7
1 5 10
2 4 2
3 5 8
4 6 3
4 11 9
5 9 5
8 9 9

15
11
13
9
5
12
-1
9