// problem #76

최단경로 (다익스트라)

정점 V개, 간선 E개의 방향 그래프에서 시작점 K로부터 각 정점까지의 최단 거리를 구하시오. 모든 간선 가중치는 자연수다.

입력

첫 줄 V, E. 둘째 줄 시작점 K. 이후 E개 줄에 간선 u v w (u→v 가중치 w).

출력

1번부터 V번 정점까지 최단거리를 한 줄씩. 도달 불가면 INF.

제한

• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 300,000
• 1 ≤ w ≤ 10

예제

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

0
2
3
7
INF