최단 경로

방향 그래프와 시작 정점 K가 주어진다. K에서 각 정점까지 가는 최단 거리를 구하시오. 모든 간선의 가중치는 1 이상 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는 1 이상 10 이하의 정수이다. 같은 순서의 두 정점 사이에 간선이 여러 개 있을 수 있다.

총 V줄을 출력한다. i번째 줄에는 K에서 i번 정점까지의 최단 거리를 출력한다. 시작 정점 자신은 0을 출력한다. K에서 도달할 수 없는 정점은 INF를 출력한다.