Solution.java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
    final static int INF = Integer.MAX_VALUE>>1;
    
    public void solve()  throws IOException {
        for (int kase = nextInt(); kase > 0; --kase) {
            int n = nextInt();
            int m = nextInt();
            int[][] g = new int[n+1][n+1];
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    g[i][j] = INF;
                }
            }
            for (int i = 0; i < m; ++i) {
                int u = nextInt();
                int v = nextInt();
                int cost = nextInt();
                g[u][v] = g[v][u] = Math.min(g[u][v], cost);
            }
            int src = nextInt();
            
            final boolean[] seen = new boolean[n+1];
            final int[] dist = new int[n+1];
            NavigableSet<Integer> pq = new TreeSet<Integer>(new Comparator<Integer>() {
                @Override
                public int compare(Integer u, Integer v) {
                    if (dist[u] == dist[v]) return u-v;
                    return Integer.compare(dist[u], dist[v]);
                }
            });
            
            for (int i = 1; i <= n; ++i) {
                dist[i] = INF;
            }
            dist[src] = 0;
            pq.add(src);
            
            while (!pq.isEmpty()) {
                final int u = pq.pollFirst();
                seen[u] = true;
                for (int v = 1; v <= n; ++v) {
                    if (!seen[v] && g[u][v] < INF && dist[u] + g[u][v] < dist[v]) {
                        pq.remove(v);
                        dist[v] = dist[u] + g[u][v];
                        pq.add(v);
                    }
                }
            }
            
            for (int i = 1; i <= n; ++i) {
                if (i != src) {
                    out.print((dist[i] >= INF ? -1l : dist[i]) + " ");
                }
            }
            out.println();
        }
    }
    
    BufferedReader in;
    StringTokenizer st;
    PrintWriter out;
    
    public Solution() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            st = new StringTokenizer("");
            solve();
        } catch (Exception e) {
            // whatever
        } finally {
            out.close();
        }
    }
    
    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null) {
                return null;
            }
            st = new StringTokenizer(line);
        }
        return st.nextToken();
    }
    
    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public static void main(String[] args) {
        new Solution();
    }
}