package basic.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


/*
특정 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘.

음수 가중치가 있을 경우에는 쓸 수 없음.

해당 문제에선 방향 없는 그래프를 기준.
 */
public class Dijkstra {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static StringBuilder sb = new StringBuilder();

    static int[] distance;

    static Map<Integer, List<Node>> graph = new HashMap<>();
    
    public static void main(String[] args) throws IOException {

        //Node의 개수
        int N = Integer.parseInt(br.readLine());

        //간선의 개수
        int E = Integer.parseInt(br.readLine());        
        
        //0 은 사용하지 않고 1 ~ N를 사용하며 특정 Node 부터 다른 Node들 까지의 거리.
        init(N);

        input(E);

        //입력 특정 노드
        dijkstra(Integer.parseInt(br.readLine()));

        printDistance();
    }
    //다익스트라 알고리즘
    private static void dijkstra(int base){
        //우선 순위 큐를 이용.
        PriorityQueue<Node> queue = new PriorityQueue<>(
                Comparator.comparingInt(node -> node.cost)
        );

        //시작점을 Queue에 추가한 채로 시작
        queue.add(new Node(base, 0));

        //중요 포인트
        distance[base] = 0;

        //Queue를 빼고 시작
        while(!queue.isEmpty()){
            //가장 최근의 노드를 poll
            Node now = queue.poll();

            //만약 추가하려는 값이 기존 최솟 값보다 크거나 같다면
            //같은 과정이 반복될테니 제외
            //이때 now.cost와 distance[now.to] 가 같은 경우는 최솟값을 최초로 집어 넣을 때만 해당
            if(now.cost > distance[now.to]) continue;

            //값의 갱신이 이루어져야한다면 해당 Node와 이어진 모든 Node들을 탐색
            for(Node next : graph.get(now.to)){
                //다음으로 이어지는 Cost를 구함.
                int nextDistance = now.cost + next.cost;

                //이어지는 cost가 최신 distance보다 작을 경우
                if(nextDistance < distance[next.to]){
                    //해당 값을 Queue에 추가.
                    distance[next.to] = nextDistance;
                    queue.add(new Node(next.to, nextDistance));
                }
            }
        }
    }

    //초기화 과정
    private static void init(int N) {
        distance = new int[N +1];

        //거리의 초기값을 최댓값으로 지정.
        Arrays.fill(distance,Integer.MAX_VALUE);

        //Graph 초기화
        for(int i = 1; i<= N; i++){
            graph.put(i, new ArrayList<>());
        }
    }
    //입력 과정
    private static void input(int E) throws IOException {
        StringTokenizer st;

        //그래프 입력
        for(int i = 0; i< E; i++){
            //입력의 형태는 (from) (to) (cost)
            st = new StringTokenizer(br.readLine());

            //시작 노드
            int from = Integer.parseInt(st.nextToken());
            //도착 노드
            int to = Integer.parseInt(st.nextToken());
            //비용
            int cost = Integer.parseInt(st.nextToken());
            
            //양 방향이기 때문에 둘 모두에 입력
            graph.get(from).add(new Node(to, cost));
            graph.get(to).add(new Node(from, cost));
        }
    }
    //결과 출력 과정
    private static void printDistance() {
        int count = 0 ;
        for(int i : distance){
            if(count==0){
                count++;
                continue;
            }

            if(i == Integer.MAX_VALUE)
                sb.append(String.format("%3s", "INF")).append(" ");
            else
                sb.append(String.format("%3d", i)).append(" ");
        }

        System.out.print(sb);
    }

    static class Node{
        int to;
        int cost;

        public Node(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }
}

//Test Case 1
/*
입력
5
6
1 2 2
1 3 3
2 3 2
2 4 4
3 4 1
4 5 1
1

0   2   3   4   5
*/
//Test Case 2
/*
입력
4
4
1 2 1
2 3 2
3 4 3
1 4 10
1

출력
0   1   3   6
*/
//Tast Case 3
/*
입력
3
2
1 2 5
2 3 2
2

출력
 7   0   2
 */