Dijkstra

// Working program with FastReader
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Scanner;
import java.util.*;
public class Main {
    static Scanner s = new Scanner(System.in);
    static PriorityQueue<Pair> heap = new PriorityQueue<>();
    static int n = s.nextInt();
    static int m = s.nextInt();
    static int [] dist = new int [n];
    static int start = s.nextInt();
    static ArrayList<Pair> [] a = new ArrayList[n];
    static int [] used = new int [n];
    public static void main(String[] args) {
        start--;
        for (int i = 0; i < n; i++) {
            a[i] = new ArrayList<>();
            if (i == start) heap.add(new Pair(0, i));
            else{
                dist[i] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < m; i++) {
            int k1 = s.nextInt();
            int k2 = s.nextInt();
            int w = s.nextInt();
            k1--;
            k2--;
            a[k1].add(new Pair(k2, w));
            a[k2].add(new Pair(k1, w));
        }
        while (heap.size() != 0){
            int p = heap.remove().y;
            if (used[p] == 1) continue;;
            used[p] = 1;
            for (Pair iter:a[p]) {
                if (dist[p] + iter.y < dist[iter.x]){
                    dist[iter.x] = dist[p] + iter.y;
                    heap.add(new Pair(dist[iter.x], iter.x));
                }
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.print(dist[i] + " ");
        }
        System.out.println();
    }
}
class Pair implements Comparable<Pair>{
    int x;
    int y;
    Pair(int x, int y){
        this.x = x;
        this.y = y;
    }
    public int compareTo(Pair p2) {
        if (this.x == p2.x){
            return this.y - p2.y;
        }
        else return this.x - p2.x;
    }
}