Description

给你一个有向有环图，不过没有负环

希望求出每个点的最短回路

Format

Input

第一行给出N，M，代表点数与边数

接下M行，每行3个数字a,b,c代表从a到b有边权为c

c<=1e5，存在重边

N,M<=2000

Output

如题 ，如果没有的话，输出-1

Samples

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