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()