N개의 정점과 M개의 방향성 간선으로 이루어진 그래프가 주어집니다. 각 간선은 u번 정점에서 v번 정점으로 향하며, 그 가중치는 w입니다.

시작 정점 K가 주어졌을 때, K에서 출발하여 다른 모든 정점으로 가는 최단 경로의 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 공백을 사이에 두고 주어진다.

둘째 줄에는 시작 정점의 번호 K가 주어진다.

셋째 줄부터 M개의 줄에 걸쳐 각 간선의 정보인 세 정수 u, v, w가 공백을 사이에 두고 주어진다.

이는 u번 정점에서 v번 정점으로 향하는 가중치가 w인 방향성 간선이 존재함을 의미한다.

출력

첫째 줄부터 N개의 줄에 걸쳐, i번째 줄에 시작 정점 K에서 i번 정점으로 가는 최단 경로의 비용을 출력한다.

자기 자신으로 가는 비용은 0으로 출력하며, 만약 시작 정점 K에서 i번 정점으로 갈 수 있는 경로가 존재하지 않는 경우에는 INF를 출력한다.

제한 사항

• 1 ≤ N ≤ 1,000
• 1 ≤ M ≤ 100,000
• 1 ≤ K ≤ N
• 1 ≤ u, v ≤ N
• 1 ≤ w ≤ 10,000 (w는 정수)
• 동일한 시작점과 도착점을 갖는 간선이 여러 개 존재할 수 있습니다. (중복 간선 허용)

예제 입력 1

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

예제 출력 1

0
2
4
5
INF