AT_abc191_e [ABC191E] Come Back Quickly

题目描述

在 AtCoder 国，有 $N$ 个城镇，编号为 $1$ 到 $N$，以及 $M$ 条道路，编号为 $1$ 到 $M$。
第 $i$ 条道路是从城镇 $A_i$ 到城镇 $B_i$ 的单向道路，通行需要 $C_i$ 分钟。可能存在 $A_i = B_i$ 的情况，也可能存在多条道路连接同一对城镇。
高桥君打算在这个国家散步。他将“正确的散步路线”定义为：从某个城镇出发，经过至少一条道路，最终回到出发的城镇的路径。
请你对于每个城镇，判断是否存在从该城镇出发的正确散步路线。如果存在，请求出经过这样的路线所需的最短时间。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$A_3$ $B_3$ $C_3$
$\vdots$
$A_M$ $B_M$ $C_M$

输出格式

请输出 $N$ 行。对于第 $i$ 行：

• 如果存在从城镇 $i$ 出发的正确散步路线，输出经过该路线所需的最短时间。
• 如果不存在，输出 $-1$。

输入输出样例 #1

输入 #1

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

输出 #1

30
30
30
-1

输入输出样例 #2

输入 #2

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

输出 #2

10
20
30
20

输入输出样例 #3

输入 #3

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

输出 #3

-1
-1
40
40

说明/提示

限制条件

• $1 \leq N \leq 2000$
• $1 \leq M \leq 2000$
• $1 \leq A_i \leq N$
• $1 \leq B_i \leq N$
• $1 \leq C_i \leq 10^5$
• 输入均为整数

样例解释 1

通过道路 $1, 2, 3$，城镇 $1, 2, 3$ 形成了一个环，绕一圈需要 $30$ 分钟。从城镇 $4$ 可以到达城镇 $1, 2, 3$，但无法回到城镇 $4$。

样例解释 2

可能存在 $A_i = B_i$ 的道路。在这种情况下，从城镇 $1$ 出发，仅使用道路 $6$，可以在 $10$ 分钟内回到城镇 $1$。

样例解释 3

请注意，可能存在多条道路连接同一对城镇。

由 ChatGPT 4.1 翻译