题目描述

AC 王国有 $n$ 座城市，编号为 $1\sim n$，然后有 $m$ 条单向道路。

国王 Gordon 现在想进行全国巡游。他会以每座城市分别作为起点开始巡游，并且最后会回到这座城市。

每次巡游一定 至少走出一条边。

现在他想知道从每座城市出发巡游的路径长度最小值。

输入格式

第一行为 $n,m(1\le n\le 2\times 10^3, n-1\le m\le 2\times 10^3)$。

往下每一行表示一条边，前两个数是有向边两端（第一个数指向第二个数），第三个数是长度。

图上可能有自环和重边，边长不大于 $10^5$。

输出格式

每座城市一行，如果从某座城市出发巡游至少走出一条边后还可以回到这座城市，输出路径长度最小值；否则输出 -1。

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

30
30
30
-1

4 6
1 2 5
1 3 10
2 4 5
3 4 10
4 1 10
1 1 10

10
20
30
20

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