题目描述

在 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)$ 应包含以下内容：

• 如果存在以城镇 $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$。
在这种情况下，我们可以只使用道路 $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

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