← 返回题目列表

AtCoder · abc191_e

E. 快点回来

中文机器翻译题面 查看原题

分数: 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

请注意,可能有多条道路连接同一对城镇。