import java.util.*;

public class Main {
    public static int n;
    public static int m;
    public static int s;
    public static List[] edges;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        s = scan.nextInt();
        edges = new List[n+1];
        for (int i = 1; i <= n; i++) {
            List<int[]> list = new ArrayList<>();
            edges[i] = list;
        }
        for (int i = 0; i < m; i++) {
            int u = scan.nextInt();
            int v = scan.nextInt();
            int w = scan.nextInt();
            int[] edge = new int[]{v, w};
            edges[u].add(edge);
        }
        int[] ans = dijkstra();
        for (int i = 1; i < ans.length; i++) {
            System.out.print(ans[i]+" ");
        }
    }

    public static int[] dijkstra() {
        int[] ans = new int[n+1];
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> ans[o1]-ans[o2]);
        Arrays.fill(ans, Integer.MAX_VALUE);
        ans[s]=0;
        queue.add(s);
        while (queue.size() != 0) {
            int cur = queue.poll();
            List<int[]> list = edges[cur];
            for (int[] edge : list) {
                if (ans[edge[0]] > edge[1] + ans[cur]) {
                    queue.remove(edge[0]);
                    ans[edge[0]] = edge[1] + ans[cur];
                    queue.add(edge[0]);
                }
            }
        }
        return ans;
    }
}