题解 | #【模板】单源最短路Ⅲ ‖ 非负权图#

import java.io.*;
import java.util.*;
import java.math.BigInteger;

public class Main {
    static void solve() {
        int n = in.nextInt(), m = in.nextInt(), s = in.nextInt();

        List<List<long[]>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int u = in.nextInt(), v = in.nextInt();
            long w = in.nextLong(); 
            g.get(u).add(new long[] {v, w});
        }

        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
        pq.add(new long[] {s, 0}); 

        long[] dis = new long[n + 1];
        Arrays.fill(dis,Long.MAX_VALUE); 
        dis[s] = 0; 

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            int u = (int) cur[0]; 
            long d = cur[1];
            if (d > dis[u]) continue;
            for (long[] edge : g.get(u)) {
                int v = (int) edge[0]; 
                long weight = edge[1];
                if (dis[u] + weight < dis[v]) {
                    dis[v] = dis[u] + weight;
                    pq.add(new long[] {v, dis[v]});
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (dis[i] == Long.MAX_VALUE) {
                out.print("-1 ");
            } else {
                out.print(dis[i] + " ");
            }
        }
    }

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    static FastReader in = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);

    static class FastReader {
        static BufferedReader br;
        static StringTokenizer st;

        FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            String str = "";
            while (st == null || !st.hasMoreElements()) {
                try {
                    str = br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st = new StringTokenizer(str);
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next()); 
        }
    }
}