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