// SPDX-License-Identifier: BSD-3-Clause

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

public class Main {
    static class Task {
        public static final String INPUT_FILE = "in";
        public static final String OUTPUT_FILE = "out";

        static final long INF = Long.MAX_VALUE / 4;
        static int N, M, S;
        static int[] head, to, cost, nxt;
        static int edgeCnt;

        public class DijkstraResult {
            long[] d;

            DijkstraResult(long[] _d) {
                d = _d;
            }
        }

        public void solve() {
            readInput();
            writeOutput(getResult());
        }

        /* ============================ Citire ============================ */
        private void readInput() {
            try {
                Scanner sc = new Scanner(new BufferedReader(new FileReader(INPUT_FILE)));
                N = sc.nextInt();
                M = sc.nextInt();
                S = sc.nextInt();

                // Inițializăm lista de adiacență folosind structura statică
                head = new int[N + 1];
                Arrays.fill(head, -1);
                to = new int[2 * M];
                cost = new int[2 * M];
                nxt = new int[2 * M];
                edgeCnt = 0;

                for (int i = 0; i < M; i++) {
                    int u = sc.nextInt();
                    int v = sc.nextInt();
                    int c = sc.nextInt();
                    addEdge(u, v, c);
                    addEdge(v, u, c);
                }
                sc.close();

            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        /* ============================ Scriere ============================ */
        private void writeOutput(DijkstraResult res) {
            try {
                BufferedWriter bw = new BufferedWriter(new FileWriter(OUTPUT_FILE));
                StringBuilder sb = new StringBuilder();
                for (int i = 1; i <= N; i++) {
                    sb.append(res.d[i] >= INF / 2 ? -1 : res.d[i]).append(' ');
                }
                sb.append('\n');
                bw.write(sb.toString());
                bw.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        /* ============================ Dijkstra ============================ */

        static void addEdge(int u, int v, int w) {
            to[edgeCnt] = v;
            cost[edgeCnt] = w;
            nxt[edgeCnt] = head[u];
            head[u] = edgeCnt++;
        }

        private DijkstraResult getResult() {
            long[] dist = new long[N + 1];
            Arrays.fill(dist, INF);
            dist[S] = 0;

            int[] heap = new int[N + 1];
            int[] pos = new int[N + 1];
            int heapSize = 1;
            heap[1] = S;
            pos[S] = 1;

            while (heapSize > 0) {
                int u = heap[1];
                pos[u] = 0;
                heap[1] = heap[heapSize];
                pos[heap[1]] = 1;
                heapSize--;
                heapifyDown(heap, pos, dist, heapSize, 1);

                for (int e = head[u]; e != -1; e = nxt[e]) {
                    int v = to[e];
                    long nd = dist[u] + cost[e];
                    if (nd < dist[v]) {
                        dist[v] = nd;
                        if (pos[v] == 0) {
                            heapSize++;
                            heap[heapSize] = v;
                            pos[v] = heapSize;
                            heapifyUp(heap, pos, dist, heapSize);
                        } else {
                            heapifyUp(heap, pos, dist, pos[v]);
                        }
                    }
                }
            }
            return new DijkstraResult(dist);
        }

        static void heapifyUp(int[] heap, int[] pos, long[] dist, int i) {
            while (i > 1) {
                int p = i >>> 1;
                if (dist[heap[p]] <= dist[heap[i]]) break;
                swap(heap, pos, p, i);
                i = p;
            }
        }

        static void heapifyDown(int[] heap, int[] pos, long[] dist, int heapSize, int i) {
            while (true) {
                int l = i << 1;
                int r = l | 1;
                int smallest = i;
                if (l <= heapSize && dist[heap[l]] < dist[heap[smallest]]) smallest = l;
                if (r <= heapSize && dist[heap[r]] < dist[heap[smallest]]) smallest = r;
                if (smallest == i) break;
                swap(heap, pos, i, smallest);
                i = smallest;
            }
        }

        static void swap(int[] heap, int[] pos, int i, int j) {
            int vi = heap[i], vj = heap[j];
            heap[i] = vj;
            heap[j] = vi;
            pos[vi] = j;
            pos[vj] = i;
        }
    }

    public static void main(String[] args) {
        new Task().solve();
    }
}