快点回来

题目描述

AtCoder 国有 $N$ 个町，编号为町 $1$ 到町 $N$，以及 $M$ 条道路，编号为道路 $1$ 到道路 $M$。

道路 $i$ 是从町 $A_i$ 到町 $B_i$ 的单行道，通行需要 $C_i$ 分钟。可能有 $A_i = B_i$，也可能有连接同一组町的多条道路。

高桥君打算在这个国家散步。从某个町出发，经过 $1$ 条以上道路，回到出发町的路径称为正确的散步路径。

对每个町，请判断是否存在从该町出发的正确散步路径。如果存在，求经过这样的路径所需时间的最小值。

输入格式

输入按以下格式从标准输入给出：

$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$ 的道路。

在这种情况下，从町 $1$ 出发，只使用道路 $6$ 就能用 $10$ 分钟回到町 $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

注意：可能存在连接同一组町的多条道路。

数据范围

• $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$
• 输入均为整数