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

//Problem Page: https://www.hackerrank.com/challenges/dijkstrashortreach/problem

public class Solution {

    static class Node implements Comparable<Node>{
        int vertex;
        int w;
        public Node(int d, int w){
            vertex=d;
            this.w=w;
        }
        public int compareTo(Node o){
            return this.w - o.w;
        }

        public String toString(){
            return ("v:"+vertex+" W:"+w);
        }

    }

    // Complete the shortestReach function below.
    static int[] shortestReach(int n, int[][] edges, int s) {


            HashMap<Integer, ArrayList<Node>> hm = new HashMap<Integer, ArrayList<Node>>();
            int e = edges.length;
            for(int i=0;i<e;i++){
                int u = edges[i][0];
                int v = edges[i][1];
                int d = edges[i][2];
                if(!hm.containsKey(u)){
                    hm.put(u,new ArrayList<Node>());
                }
                hm.get(u).add(new Node(v,d));
                if(!hm.containsKey(v)){
                    hm.put(v, new ArrayList<Node>());
                }
                hm.get(v).add(new Node(u,d));
            }

           //System.out.println(hm);

            PriorityQueue<Node> pq = new PriorityQueue<Node>();
            pq.add(new Node(s,0));


            //in central place

            int d[] = new int[n+1];
            for(int i=0;i<=n;i++){
                d[i]=Integer.MAX_VALUE;
            }
            d[s]=0;

            while(pq.size()>0){
                Node u = pq.poll();
                for(int i=0;i<hm.get(u.vertex).size();i++){
                    Node v = hm.get(u.vertex).get(i);
                    if(d[v.vertex]>d[u.vertex]+v.w){
                        d[v.vertex]=d[u.vertex]+v.w;
                        pq.add(v);
                    }
                }
            }

            int ans[] = new int[n-1];
            int j=0;
            for(int i=1;i<=n;i++){
                if(i!=s){
                    ans[j]=d[i];
                    j++;
                }

            }

            for(int i=0;i<n-1;i++){
                if(ans[i]==Integer.MAX_VALUE){
                    ans[i]=-1;
                }
            }

            return ans;





    }

    //private static final Scanner scanner = new Scanner(System.in);

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

        FastReader scanner = new FastReader();

        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        //scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            String[] nm = scanner.nextLine().split(" ");

            int n = Integer.parseInt(nm[0]);

            int m = Integer.parseInt(nm[1]);

            int[][] edges = new int[m][3];

            for (int i = 0; i < m; i++) {
                String[] edgesRowItems = scanner.nextLine().split(" ");
                //scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

                for (int j = 0; j < 3; j++) {
                    int edgesItem = Integer.parseInt(edgesRowItems[j]);
                    edges[i][j] = edgesItem;
                }
            }

            int s = scanner.nextInt();
            //scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] result = shortestReach(n, edges, s);

            for (int i = 0; i < result.length; i++) {
                bufferedWriter.write(String.valueOf(result[i]));

                if (i != result.length - 1) {
                    bufferedWriter.write(" ");
                }
            }

            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        //scanner.close();
    }
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

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

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

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

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

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}