Come Back Quickly

题目描述

在 AtCoder 共和国，有 $N$ 个城镇，编号为 $1$ 到 $N$，以及 $M$ 条道路，编号为 $1$ 到 $M$。
道路 $i$ 是一条从城镇 $A_i$ 到城镇 $B_i$ 的单向道路，通过它需要 $C_i$ 分钟。可能存在 $A_i = B_i$ 的情况，并且相同一对城镇之间可能有多条道路。
Takahashi 正在考虑在乡间散步。我们称一条步行为有效的，当且仅当它经过一个或多个道路并回到出发的城镇。
对于每个城镇，判断是否存在从该城镇出发的有效步行。此外，如果存在，则找出这样的步行所需的最短时间。

输入格式

输入按以下格式从标准输入给出： $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

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$ 输入中的所有值均为整数。通过道路 $1, 2, 3$，城镇 $1, 2, 3$ 形成了一个环，绕行一圈需要 $30$ 分钟。
从城镇 $4$ 可以到达城镇 $1, 2, 3$，但无法返回到城镇 $4$。
可能存在 $A_i = B_i$ 的道路。
在这里，我们可以仅使用道路 $6$ 从城镇 $1$ 出发并返回到该城镇。
注意相同一对城镇之间可能有多条道路。

标签: AtCoder|abc191E

来源

AtCoder|abc191E