题目描述

小婷正在研究一个有向交通网络。网络中有 $N$ 座城市和 $M$ 条有向道路，城市编号为 $1$ 到 $N$。第 $i$ 条道路从城市 $A_i$ 通向城市 $B_i$，通过它需要 $C_i$ 的时间。

道路只能按照规定方向通行。网络中允许存在从一座城市直接回到自身的自环，也允许两座城市之间存在多条方向相同、耗时不同的道路。

对于每一座城市 $s$，小婷都希望找到一条旅行路线：从城市 $s$ 出发，至少经过一条道路，最后重新回到城市 $s$。路线中可以经过其他城市，也可以重复经过城市或道路。

请分别求出从每座城市出发并返回该城市的最短总时间。如果某座城市不存在这样的非空往返路线，则输出 $-1$。

输入格式

第一行输入两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行输入三个整数 $A_i,B_i,C_i$，描述一条有向道路。

输出格式

输出 $N$ 行。第 $i$ 行输出从城市 $i$ 出发、至少经过一条道路并返回城市 $i$ 的最短时间；若不存在，输出 $-1$。

4 4
1 2 5
2 3 10
3 1 15
4 3 20

30
30
30
-1

样例说明 #1

城市 $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

样例说明 #2

城市 $1$ 有一条耗时为 $10$ 的自环，它本身就是一条合法的非空往返路线。

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\le2000$，$1\le M\le2000$，$1\le A_i,B_i\le N$，$1\le C_i\le10^5$。允许自环和重边，输入中的所有数均为整数。