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 \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 翻译