function heapMoveUp(hArr, indMap, distance, n) {
    let ind = indMap[n];
    while (ind > 0) {
        const p = ind - 1 >> 1;
        if (distance[hArr[p]] > distance[hArr[ind]]) { // comparison
            [hArr[p], hArr[ind]] = [hArr[ind], hArr[p]];
            indMap[hArr[p]] = p;
            indMap[hArr[ind]] = ind;
            ind = p;
        } else {
            break;
        }
    }
}
function heapMoveDown(hArr, indMap, distance, hSize, n) {
    let ind = indMap[n];
    while (ind < hSize) {
        let c = 2 * ind + 1;
        if (c >= hSize) break;

        const s = c + 1;
        if (s < hSize && distance[hArr[c]] > distance[hArr[s]]) { // comparison
            c = s;
        }

        if (distance[hArr[ind]] <= distance[hArr[c]]) break; // comparison

        [hArr[ind], hArr[c]] = [hArr[c], hArr[ind]];
        indMap[hArr[ind]] = ind;
        indMap[hArr[c]] = c;
        ind = c;
    }
}

function shortestReach(n, edges, s) {
    const graph = {};
    for (let i = 1; i <= n; i++) {
        graph[i] = {};
    }
    for (const [begin, end, weight] of edges) {
        if ((graph[begin][end] ?? Infinity) < weight) continue;
        graph[begin][end] = weight;
        graph[end][begin] = weight;
    }

    const result = {};
    const distance = { [s]: 0 };
    const indMap = {};
    const hArr = [];
    let hSize = 0;
    function insertHeap(n) {
        const ind = hSize;
        hArr[hSize++] = n;
        indMap[n] = ind;
        heapMoveUp(hArr, indMap, distance, n);
    }
    function deleteHeap() {
        const ret = hArr[0];
        hArr[0] = hArr[--hSize];
        delete indMap[ret];
        indMap[hArr[0]] = 0;
        heapMoveDown(hArr, indMap, distance, hSize, hArr[0]);
        return ret;
    }
    insertHeap(s);

    while (hSize > 0) {
        const nextShortest = deleteHeap();
        const minDis = distance[nextShortest];
        result[nextShortest] = minDis;

        for (const [node, weight] of Object.entries(graph[nextShortest])) {
            if (result[node] !== undefined) continue;

            const isInsert = distance[node] === undefined;
            const nDis = minDis + weight;
            if (isInsert) {
                distance[node] = nDis;
                insertHeap(node);
            } else if (distance[node] > nDis) {
                distance[node] = nDis;
                heapMoveUp(hArr, indMap, distance, node);
            }
        }
    }

    const ret = [];
    for (let i = 1; i <= n; i++) {
        if (i === s) continue;
        ret.push(result[i] ?? -1);
    }
    return ret;
}

function shortestReach(n, edges, s) {
    const graph = {};
    for (let i = 1; i <= n; i++) {
        graph[i] = {};
    }
    for (const [begin, end, weight] of edges) {
        if ((graph[begin][end] ?? Infinity) < weight) continue;
        graph[begin][end] = weight;
        graph[end][begin] = weight;
    }

    const result = {};
    const distance = { [s]: 0 };
    const candidates = new Set([s]);
    while (candidates.size) {
        let nextShortest;
        let minDis = Infinity;
        for (const c of candidates) {
            if (distance[c] < minDis) {
                nextShortest = c;
                minDis = distance[c];
            }
        }
        result[nextShortest] = minDis;
        candidates.delete(nextShortest);

        for (const [node, dis] of Object.entries(graph[nextShortest])) {
            if (result[node] !== undefined) continue;

            distance[node] = Math.min(
                distance[node] ?? Infinity,
                minDis + dis
            );
            candidates.add(node);
        }
    }

    const ret = [];
    for (let i = 1; i <= n; i++) {
        if (i === s) continue;
        ret.push(result[i] ?? -1);
    }
    return ret;
}

import os
import heapq

class Graph:
    def __init__(self, numberOfNodes, directed=True):
        self.__numberOfNodes = numberOfNodes
        self.__directed = directed
        self.__adjmatrix = [[0 for _ in range(numberOfNodes)] for _ in range(numberOfNodes)]

    def add_edge(self, node1, node2, weight=1):
        self.__adjmatrix[node1][node2] = weight
        if not self.__directed:
            self.__adjmatrix[node2][node1] = weight

    def dijkstra(self, start_node):
        distances = [float('inf')] * self.__numberOfNodes
        distances[start_node] = 0
        visited = set()
        pq = [(0, start_node)]

        while pq:
            current_distance, current_node = heapq.heappop(pq)
            if current_node in visited:
                continue

            visited.add(current_node)

            for neighbor in range(self.__numberOfNodes):
                if self.__adjmatrix[current_node][neighbor] > 0:
                    new_distance = current_distance + self.__adjmatrix[current_node][neighbor]
                    if neighbor==1:
                        print(new_distance)
                    if new_distance < distances[neighbor]:
                        distances[neighbor] = new_distance
                        heapq.heappush(pq, (new_distance, neighbor))
        print(f"distances: {distances}")
        return distances


def shortestReach(n, edges, s):
    graph = Graph(n, directed=False)
    for edge in edges:
        graph.add_edge(edge[0] - 1, edge[1] - 1, edge[2])

    result = graph.dijkstra(s - 1)
    result.pop(s - 1)

    updated_list = [-1 if x == float('inf') else x for x in result]
    print(f"result:{updated_list}")
    return updated_list

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for _ in range(t):
        n, m = map(int, input().split())

        edges = []
        for _ in range(m):
            edges.append(list(map(int, input().split())))

        s = int(input().strip())

        result = shortestReach(n, edges, s)

        fptr.write(' '.join(map(str, result)))
        fptr.write('\n')

    fptr.close()