#84최단경로

어떤 방향그래프와 그 안의 한 시작 정점이 주어진다. 이 시작 정점에서 출발해 그래프 안의 다른 모든 정점까지 가는 최단 경로의 길이를 구하는 프로그램을 작성한다. 그래프의 모든 간선에는 가중치가 있으며, 가중치는 항상 10 이하의 자연수이다.

첫 줄에는 정점의 개수 V와 간선의 개수 E가 공백으로 구분되어 주어진다(1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000). 정점에는 1번부터 V번까지 번호가 붙어 있다고 본다. 두 번째 줄에는 출발 지점이 되는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 이어지는 E개의 줄에는 각 간선의 정보를 나타내는 세 정수 u, v, w가 한 줄에 하나씩 주어지며, 이는 "정점 u에서 정점 v로 향하는, 가중치가 w인 간선이 있다"는 뜻이다. u와 v는 항상 서로 다른 값이고 w는 10 이하의 자연수이다. 또한 같은 두 정점 사이를 잇는 간선이 여러 개 주어질 수 있다는 점에 유의한다.

총 V줄에 걸쳐 결과를 출력하되, i번째 줄에는 시작 정점에서 i번 정점까지의 최단 경로 길이를 출력한다. 이때 시작 정점 자기 자신으로 가는 경로의 길이는 0으로 출력하고, 시작 정점에서 도달할 수 없는 정점에 대해서는 INF를 출력한다.