\(N\)개의 정점과 \(M\)개의 간선으로 이루어진 방향 그래프가 있다.

각 간선에는 가중치가 있으며, 가중치는 음수일 수도 있다.

\(1\)번 정점에서 출발하여 \(2\)번 정점부터 \(N\)번 정점까지의 최단 거리를 각각 구하시오.

단, \(1\)번 정점에서 도달할 수 있는 음수 사이클이 존재한다면 최단 거리를 정할 수 없으므로 \(-1\)만 출력한다.

입력 설명

첫 번째 줄에 정점의 개수 \(N\)과 간선의 개수 \(M\)이 공백으로 구분되어 입력된다.

두 번째 줄부터 \(M\)개의 줄에 걸쳐 간선의 정보 \(A\), \(B\), \(C\)가 공백으로 구분되어 입력된다.

이는 \(A\)번 정점에서 \(B\)번 정점으로 가는 가중치 \(C\)의 방향 간선이 존재한다는 뜻이다.

출력 설명

\(1\)번 정점에서 도달할 수 있는 음수 사이클이 존재하면 첫 번째 줄에 \(-1\)을 출력한다.

음수 사이클이 존재하지 않으면 \(2\)번 정점부터 \(N\)번 정점까지의 최단 거리를 한 줄에 하나씩 출력한다.

단, \(1\)번 정점에서 도달할 수 없는 정점은 \(-1\)을 출력한다.

제한

\(2 <= N <= 500\)

\(1 <= M <= 6000\)

\(1 <= A, B <= N\)

\(-10000 <= C <= 10000\)

입력 예시

5 7
1 2 6
1 3 7
2 3 8
2 4 5
2 5 -4
3 4 -3
4 5 9

출력 예시

6
7
4
2