Dijkstra

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 = [source]
        distance = [maxsize] * self.v
        distance[source] = 0
        heapify(Q)

        while Q:

            u = heappop(Q)

            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, v)

        return distance[1:]



def shortestReach(n, edges, s):

    g = Graph(n)
    for tpl in edges:
        g.add_edges(tpl[0], tpl[1], tpl[2])

    shortest_distance = g.dijkstra(s)

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

        edges = []

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

        s = int(input())

        result = shortestReach(n, edges, s)

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