分数: 500 点
问题陈述
在AtCoder共和国,有 N 城镇编号 1 通过 N 和 M 道路编号 1 通过 M.
路 i 是一条从城镇出发的单向道路 A_i 到镇 B_i,并且需要 C_i 分钟完成。有可能的是 A_i = B_i,并且可能有多条道路连接同一对城镇。
高桥正在考虑去乡下散步。我们会叫散步 有效 当它经过一条或多条道路并返回其出发的城镇时。
对于每个城镇,确定是否存在从该城镇开始的有效步行。此外,如果答案是肯定的,请找出这样的步行所需的最短时间。
约束
- 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) 应包含以下内容:
- 如果有从 Town 开始的有效步行 i,这样步行所需的最短时间;
- 否则,
-1.
示例输入 1
4 4 1 2 5 2 3 10 3 1 15 4 3 20
示例输出 1
30 30 30 -1
道路 1, 2, 3, 城镇 1, 2, 3 形成一个环,需要 30 分钟一圈。
来自城镇 4,我们可以去城镇 1, 2, 3,但是我们无法返回城镇 4.
示例输入 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
可能有一条路 A_i = B_i.
在这里,我们可以使用just Road 6 从城镇出发 1 并返回那个城镇。
示例输入 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
请注意,可能有多条道路连接同一对城镇。