모든 곳까지 최단 거리

첫 줄에 노드의 수 n (1 이상 100000 이하) 과 간선의 수 m (0 이상 4000 이하) 이 주어집니다. 이어서 m개의 줄에 방향 간선 u v w 가 주어집니다. u 에서 v 로 가는 비용이 w (1 이상 1000000 이하) 입니다.

1번 노드에서 각 노드 1..n 까지의 최단 거리를 한 줄에 하나씩 출력하세요. 갈 수 없는 노드는 -1 을 출력합니다. (1번 자신은 0)

예시

입력

4 5
1 2 1
1 3 5
2 3 2
2 4 7
3 4 1

출력

0
1
3
4