题目描述

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

输入格式

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

$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

题目大意

$n$ 个城市 $m$ 条道路，每条路 $a_i$ , $b_i$ , $c_i$，表示 $a_i$ 到 $b_i$ 的单向路，需要花费 $c_i$ 分钟走到，可能会有重边和自环。问能否从第 $i$ 个城市出发然后回到该城市形成一个环？可以输出最短时间，否则 $-1$ 。

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

30
30
30
-1

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

10
20
30
20

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

提示

制約

• $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$
• 入力は全て整数

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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