import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // num nodes
        int m = Integer.parseInt(st.nextToken()); // num edges
        int start = Integer.parseInt(st.nextToken()) - 1; // starting node

        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1; // node 1
            int b = Integer.parseInt(st.nextToken()) - 1; // node 2
            int c = Integer.parseInt(st.nextToken()); // edge weight

            adj.get(a).add(new Pair(b, c)); // directed graph
        }

        long[] dist = dijkstra(start, adj);
        for (int i = 0; i < dist.length; i++) {
            pw.print(dist[i] + " ");
        }

        pw.close();
    }

    private static long[] dijkstra(int start, ArrayList<ArrayList<Pair>> adj) {
        long[] dist = new long[adj.size()];
        Arrays.fill(dist, Long.MAX_VALUE);

        dist[start] = 0;

        //boolean[] processed = new boolean[n];

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        pq.add(new Pair(start, 0));

        while (!pq.isEmpty()) {
            Pair head = pq.poll();

            //if (processed[head.id]) continue;
            //processed[head.id] = true;

            for (Pair nbr : adj.get(head.id)) {
                if (dist[head.id] + nbr.dist < dist[nbr.id]) {
                    dist[nbr.id] = dist[head.id] + nbr.dist;
                    pq.add(new Pair(nbr.id, dist[nbr.id]));
                }
            }
        }

        return dist;
    }
}

class Pair implements Comparable<Pair> {
    public int id;
    public long dist;

    public Pair(int id, long dist) {
        this.id = id;
        this.dist = dist;
    }

    @Override
    public int compareTo(Pair o) {
        long diff = this.dist - o.dist;
        if (diff < 0) return -1;
        if (diff > 0) return 1;
        return 0;
    }
}