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

public class Main {
public static class Node {
        int val, w;
        Node(int val, int weight) {
            this.val = val;
            this.w = weight;
        }
    }
  public static int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S)
  {
     // Write your code here
        int[] ans = new int[V];
        Arrays.fill(ans, -1);
        PriorityQueue<Node> pq = new PriorityQueue<>((Node a, Node b) -> a.w - b.w);
        pq.offer(new Node(S, 0));

        while(!pq.isEmpty()) {
            Node temp = pq.poll();
            if (ans[temp.val] != -1) continue;
            ans[temp.val] = temp.w;

            for (List<Integer> next : adj.get(temp.val)) {
                pq.offer(new Node(next.get(0), temp.w + next.get(1)));
            }
        }

        return ans;
  }

  public static void main(String args[]) throws IOException {

        BufferedReader read =
            new BufferedReader(new InputStreamReader(System.in));
            String str[] = read.readLine().trim().split(" ");
            int V = Integer.parseInt(str[0]);
            int E = Integer.parseInt(str[1]);

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

            int i=0;
            while (i++<E) {
                String S[] = read.readLine().trim().split(" ");
                int u = Integer.parseInt(S[0]);
                int v = Integer.parseInt(S[1]);
                int w = Integer.parseInt(S[2]);
                ArrayList<Integer> t1 = new ArrayList<Integer>();
                ArrayList<Integer> t2 = new ArrayList<Integer>();
                t1.add(v);
                t1.add(w);
                t2.add(u);
                t2.add(w);
                adj.get(u).add(t1);
                adj.get(v).add(t2);
            }

            int S = Integer.parseInt(read.readLine());

            int[] ptr = dijkstra(V, adj, S);

            for(i=0; i<V; i++)
                System.out.print(ptr[i] + " ");
            System.out.println();
        }
}