配点 : $500$ 点

問題文

AtCoder 国には、町 $1$ から町 $N$ までの $N$ 個の町と、道路 $1$ から道路 $M$ までの $M$ 本の道路があります。 道路 $i$ は町 $A_i$ から町 $B_i$ への一方通行で、通るのに $C_i$ 分かかります。$A_i = B_i$ かもしれませんし、同じ町の組を結ぶ道路が複数あるかもしれません。 高橋君はこの国で散歩をしようと考えました。ある町から出発し、$1$ 本以上の道路を通り、出発した町に帰ってくるような経路を正しい散歩経路と呼ぶことにします。 各町について、その町から出発する正しい散歩経路が存在するかを判定してください。また、存在するなら、そのような経路を通るのにかかる時間の最小値を求めてください。

制約

• $1 \le N \le 2000$
• $1 \le M \le 2000$
• $1 \le A_i \le N$
• $1 \le B_i \le N$
• $1 \le C_i \le 10^5$
• 入力は全て整数

入力

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

$N$ $M$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$A_3$ $B_3$ $C_3$

$\hspace{25pt} \vdots$

$A_M$ $B_M$ $C_M$

出力

$N$ 行に渡って出力せよ。 $i(1 \le i \le N)$ 行目には以下を出力せよ。

• 町 $i$ から出発する正しい散歩経路が存在するなら、そのような経路を通るのにかかる時間の最小値
• 存在しないなら -1

4 4
1 2 5
2 3 10
3 1 15
4 3 20

30
30
30
-1

道路 $1, 2, 3$ によって、町 $1, 2, 3$ は一周に $30$ 分かかる一つの輪のように繋がっています。 町 $4$ から町 $1, 2, 3$ に行くことはできますが、町 $4$ に帰ってくることはできません。

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

10
20
30
20

$A_i = B_i$ であるような道路が存在するかもしれません。 この場合、町 $1$ からは、道路 $6$ だけを使って $10$ 分で町 $1$ に帰ってくることができます。

4 7
1 2 10
2 3 30
1 4 15
3 4 25
3 4 20
4 3 20
4 3 30

-1
-1
40
40

同じ町の組を結ぶ道路が複数あるかもしれないことに注意してください。