Electro-Communication

2 secs 1024 MB
dyktr_06's icon dyktr_06

問題文

とある村には、NN 個の家と MM 個の電波塔があります。

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

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

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

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

制約

  • 1N,M1051 \leq N, M \leq 10^5
  • 1K1051 \leq K \leq 10^5
  • 1Ui<ViN+M1 \leq U_i < V_i \leq N + M
  • 1Ti1091 \leq T_i \leq 10^9
  • iji \neq j ならば、(Ui,Vi)(Uj,Vj)(U_i, V_i) \neq (U_j, V_j)
  • 入力はすべて整数である。

入力

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

NNMMKK
U1U_1V1V_1T1T_1
U2U_2V2V_2T2T_2
\vdots

UKU_KVKV_KTKT_K

出力

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

入出力例

入力例1
4 3 5
1 2 4
1 4 2
2 5 6
2 6 8
4 7 3
出力例1
5
6
-1
3

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

入力例2
8 5 7
1 5 10
2 4 2
3 5 8
4 6 3
4 11 9
5 9 5
8 9 9
出力例2
15
11
13
9
5
12
-1
9

Submit


Go (1.21)