import java.util.*;

public class Main {
    static int m, n, s, t, cnt = 0;
    static int[] dis;
    static int[] vis;
    static int[] head;

    static class Edge {
        int next, to, distance;
    }

    static Edge[] edge;

    static void addedge(int a, int b, int c) {
        edge[++cnt].next = head[a];
        edge[cnt].to = b;
        edge[cnt].distance = c;
        head[a] = cnt;
    }

    static void fff() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            dis[i] = (int) inf;
            vis[i] = 0;
        }
        q.add(s);
        dis[s] = 0;
        vis[s] = 1;
        while (!q.isEmpty()) {
            int u = q.poll();
            vis[u] = 0;
            for (int i = head[u]; i != 0; i = edge[i].next) {
                int v = edge[i].to;
                if (dis[v] > dis[u] + edge[i].distance) {
                    dis[v] = dis[u] + edge[i].distance;
                    if (vis[v] == 0) {
                        vis[v] = 1;
                        q.add(v);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        s = sc.nextInt();
        edge = new Edge[m + 1];
        head = new int[n + 1];
        dis = new int[n + 1];
        vis = new int[n + 1];
        init();
        for (int i = 1; i <= m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            addedge(a, b, c);
        }
        fff();
        for (int i = 1; i <= n; i++) {
            if (s == i) System.out.print(0 + " ");
            else System.out.print(dis[i] + " ");
        }
    }

    public static void init() {
        for (int i = 0; i <= m; i++) {
            edge[i] = new Edge();
        }
        for (int i = 0; i <= n; i++) {
            head[i] = 0;
        }
        for (int i = 0; i <= n; i++) {
            dis[i] = Integer.MAX_VALUE;
        }
    }
}