import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
    static Node[] nodes;
    static boolean[] visited;
    static ArrayList<Node> queue = new ArrayList<Node>();

    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        for (int j = 0; j < T; j++) {
            int N = input.nextInt();
            int M = input.nextInt();
            nodes = new Node[N + 1];
            visited = new boolean[N + 1];
            for (int i = 0; i < N + 1; i++) {
                nodes[i] = new Node();
            }
            for (int i = 0; i < N; i++) {
                int x = input.nextInt();
                int y = input.nextInt();
                int r = input.nextInt();
                nodes[x].data = x;
                nodes[y].data = y;
                nodes[x].distance = (int) 10e9;
                nodes[y].distance = (int) 10e9;
                nodes[x].addNeighbor(y, r);
                nodes[y].addNeighbor(x, r);
                if (!queue.contains(nodes[x]))
                    queue.add(nodes[x]);
                if (!queue.contains(nodes[y]))
                    queue.add(nodes[y]);
            }
            int S = input.nextInt();
            dijkstra(nodes[S]);
            for (int i = 0; i < nodes.length; i++) {
                if (nodes[i].data != 0 && nodes[i].data != S)
                    System.out.print(nodes[i].distance + " ");
            }
        }
    }

    public static void dijkstra(Node source) {
        source.distance = 0;
        while (!queue.isEmpty()) {
            Node current = getShortestDistance();
            for (int i = 0; i < current.neighbors.size(); i++) {
                if (!visited[current.neighbors.get(i)]) {
                    int newDistance = current.distance + current.getEdgeDistance(current.neighbors.get(i));
                    if (newDistance < nodes[current.neighbors.get(i)].distance) {
                        nodes[current.neighbors.get(i)].distance = newDistance;
                        nodes[current.neighbors.get(i)].previous = current.data;
                    }
                }
            }
        }
    }

    public static Node getShortestDistance() {
        Node shortest = queue.get(0);
        for (int i = 1; i < queue.size(); i++) {
            if (queue.get(i).distance < shortest.distance) {
                shortest = queue.get(i);
            }
        }
        visited[shortest.data] = true;
        return queue.remove(queue.indexOf(shortest));

    }
}

class Node {
    int data;
    int previous;
    int distance;
    ArrayList<Integer> neighbors = new ArrayList<Integer>();
    int[] edgeDistances = new int[3001];

    public void addNeighbor(int n, int r) {
        neighbors.add(n);
        edgeDistances[n] = r;
    }

    public int getEdgeDistance(int n) {
        return edgeDistances[n];
    }
}