Dijkstra_Correct_Solution

from heapq import heappop, heappush, heapify
from sys import maxsize


class Graph:
    def __init__(self, vertices):
        self.v = vertices+1
        self.cost = [[0]*(vertices+1) for _ in range(vertices+1)]

    def add_edges(self, src, dest, weight):
        if self.cost[src][dest] and self.cost[dest][src]:
            if self.cost[src][dest] > weight and self.cost[dest][src] > weight:
                self.cost[src][dest] = weight
                self.cost[dest][src] = weight
        else:
            self.cost[src][dest] = weight
            # Becouse, Given Graph is undirected.
            self.cost[dest][src] = weight

    def dijkstra(self, source):

        Q = [(0, source)]
        distance = [maxsize] * self.v
        distance[source] = 0
        heapify(Q)

        while Q:

            node_with_min_dist = heappop(Q)
            u = node_with_min_dist[1]

            for v in range(self.v):
                if self.cost[u][v] and distance[u] + self.cost[u][v] < distance[v]:
                    distance[v] = distance[u] + self.cost[u][v]
                    heappush(Q, (distance[v], v))

        return distance[1:]



def shortestReach(n, m):

    g = Graph(n)
    for _ in range(m):
        s, d, w = list(map(int, input().split()))
        g.add_edges(s, d, w)

    shortest_distance = g.dijkstra(int(input()))

    return shortest_distance



if __name__ == '__main__':

    t = int(input())

    for t_itr in range(t):
        nm = input().split()

        n = int(nm[0])

        m = int(nm[1])

        result = shortestReach(n, m)

        for i in result:
            if i == 0: continue
            elif i == maxsize: print(-1, end=' ')
            else: print(i, end=' ')
        print()