E - 快点回来

得分：$500$ 分

问题描述

在 AtCoder 共和国中，有 $N$ 个编号为 $1$ 到 $N$ 的城镇和 $M$ 条编号为 $1$ 到 $M$ 的道路。
道路 $i$ 是一条从城镇 $A_i$ 到城镇 $B_i$ 的单行道，通过它需要 $C_i$ 分钟。可能有 $A_i = B_i$，同一对城镇之间可能有多条道路。
Takahashi 想要在乡下散步。我们称一次游走为 有效，如果经过一条或多条道路并返回到游走开始的城镇。
对于每个城镇，确定是否存在一个以该城镇为起点的有效游走。此外，如果答案是肯定的，找到这样一次游走所需的最短时间。

限制

• $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$ 的道路。
在这个例子中，我们可以只使用道路 $6$ 来从城镇 $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

注意同一对城镇之间可能有多条道路。