import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.*;

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

        int n;
        int m;
        int source;

        class pqComp implements Comparator<Entry>{
            public int compare(Entry e1, Entry e2){
                return e2.dist - e1.dist;
            }
        }

        public class Entry {
            public int node;
            public int dist;

            Entry (int node, int distance){
                this.node = node;
                dist = distance;
            }
        }
        public class Edge {
            public int node;
            public int cost;

            Edge(int _node, int _cost) {
                node = _node;
                cost = _cost;
            }
        }

        @SuppressWarnings("unchecked")
        ArrayList<Edge> adj[] = new ArrayList[NMAX];

        private void readInput() {
            try {
                Scanner sc = new Scanner(new BufferedReader(new FileReader(
                                INPUT_FILE)));
                n = sc.nextInt();
                m = sc.nextInt();
                source = sc.nextInt();

                for (int i = 1; i <= n; i++) {
                    adj[i] = new ArrayList<>();
                }
                for (int i = 1; i <= m; i++) {
                    int x, y, w;
                    x = sc.nextInt();
                    y = sc.nextInt();
                    w = sc.nextInt();
                    adj[x].add(new Edge(y, w));
                }
                sc.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        private void writeOutput(ArrayList<Integer> result) {
            try {
                BufferedWriter bw = new BufferedWriter(new FileWriter(
                                OUTPUT_FILE));
                StringBuilder sb = new StringBuilder();
                for (int i = 1; i <= n; i++) {
                    sb.append(result.get(i)).append(' ');
                }
                sb.append('\n');
                bw.write(sb.toString());
                bw.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        private ArrayList<Integer> getResult() {
            // TODO: Gasiti distantele minime de la nodul source la celelalte noduri
            // folosind Dijkstra pe graful orientat cu n noduri, m arce stocat in adj.
            //  d[node] = costul minim / lungimea minima a unui drum de la source la
            //  nodul node;
            //  d[source] = 0;
            //  d[node] = -1, daca nu se poate ajunge de la source la node.
            // Atentie:
            // O muchie este tinuta ca o pereche (nod adiacent, cost muchie):
            //  adj[x].get(i).node = nodul adiacent lui x,
            //  adj[x].get(i).cost = costul.

            //Entry - int node, int dist

            ArrayList<Integer> d = new ArrayList<>();
            PriorityQueue<Entry> q = new PriorityQueue<>(new pqComp());
            int vizitat[] = new int[n+1];

            for(int i = 0; i <= n; i++){
                vizitat[i] = 0;
            }

            for (int i = 0; i <= n; i++)
                d.add(0);

            for(int i = 0; i <= n; i++){
                d.set(i,9999999);
            }

            d.set(source,0);

            q.add(new Entry(source,0));
            while(q.size() != 0){
                Entry u = q.poll();
                int aux_node = u.node;
                int aux_dist = u.dist;
                vizitat[aux_node] = 1;
                for (Edge ed : adj[aux_node]){
                    int vec = ed.node;
                    int c = ed.cost;
                    if(vizitat[vec] == 0 && d.get(vec) > d.get(aux_node) + c){
                        d.set(vec, d.get(aux_node) + c);
                        q.add(new Entry(vec,d.get(vec)));
                    }
                }
            }
            for(int i = 0; i <= n; i ++){
                if (d.get(i) == 9999999) d.set(i,-1);
            }
      return d;
        }

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

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