package main

import "fmt"
import "container/heap"

// The graph will consist of a [][]*Edge, which is a 2D slice, the first [] dimension
// is the number of nodes (thus each position represents a node) and then the second
// []*Edge dimension represents a list of *Edge elements for each node (the edges)
// that come out from that node towards another. Since it will be an undirected graph
// the created *Edge will exist in both ends/nodes.
type Edge struct {
    from, to, cost int
}

// PriorityQueue is a type for []*Edge, such that it will implement the heap
// interface (Push, Pop) and its "inherited" sort interface (Len, Swap, Less)
// Heap interface implementation referenced from:
//     https://golang.org/pkg/container/heap/
type PriorityQueue []*Edge

// Length of the PriorityQueue ([]*Edge).
// Method is implemented as per Heap->Sort interface.
func (pq PriorityQueue) Len() int {
    return len(pq)
}

// Swap two elements of the PriorityQueue and update indices in PQ.
// Method is implemented as per Heap->Sort interface.
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

// We want the PriorityQueue to prioritize items with lesser cost.
// Method is implemented as per Heap->Sort interface.
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].cost < pq[j].cost
}

// Push a new element into the PriorityQueue.
// Method is implemented as per Heap interface.
func (pq *PriorityQueue) Push(e interface{}) {
    edge := e.(*Edge)
    *pq = append(*pq, edge)
}

// Remove an element from the PriorityQueue
// Method is implemented as per Heap interface.
func (pq *PriorityQueue) Pop() interface{} {
    oldpq := *pq
    n := len(oldpq)
    edge := oldpq[n-1]
    *pq = oldpq[0 : n-1]
    return edge
}

// Dijkstra algorithm, which uses a PriorityQueue to find the shortest
// path between two nodes, giving priority to the shortest paths coming
// up in the PriorityQueue.
func dijkstra(nodes [][]*Edge, start int) []int {
    // Default value for costs is -1, this means unvisited. First visit
    // will immediately replace it, and then we'll start looking for the
    // lowest possible value.
    costs := make([]int, len(nodes))
    for i := 0; i < len(costs); i++ {
        costs[i] = -1
    }

    // Create a fake edge to the starting node, to start graph traversal from it
    st := &Edge{
        from: start,
        to:   start,
        cost: 0,
    }
    // The cost/path weight to reach the starting node will be zero.
    costs[start] = 0
    // Initialize the PriorityQueue and insert the fake edge to the 'root' node.
    pq := PriorityQueue{}
    heap.Init(&pq)
    heap.Push(&pq, st)

    // While there are elements on the PriorityQueue...
    for len(pq) > 0 {
        // Pop the element from the PQ, and then assert its type to be *Edge
        // since following Heap's interface requires elements to be interface{}
        cur := heap.Pop(&pq).(*Edge)
        // Iterate over all the edges outgoing from current node.
        // The retrieved 'cur' is just an Edge inserted previously, the current
        // node is the 'to' ~ target value of that Edge.
        for i := 0; i < len(nodes[cur.to]); i++ {
            edge := nodes[cur.to][i]
            // If the cumulative cost to this point + the cost to a neighbor node
            // is less than the registered value of the cost to that node, then
            // add that path as a possibility and register new low cost value!
            // Also push the edge if no cost has been ever registered towards the
            // target node (meaning so far first value found will be stored).
            if costs[edge.from]+edge.cost < costs[edge.to] || costs[edge.to] == -1 {
                costs[edge.to] = costs[edge.from] + edge.cost
                heap.Push(&pq, edge)
            }
        }
    }
    return costs
}

func main() {
    // t: is the number of test cases.
    var t int
    fmt.Scanf("%v", &t)
    for i := 0; i < t; i++ {
        // n: number of nodes in graph, m: number of edges in graph.
        var n, m int
        fmt.Scanf("%v %v", &n, &m)
        // 1st dimension []: number of nodes
        // 2nd dimension []*Edge: a list of Edges going out from the node at index i.
        nodes := make([][]*Edge, n)
        // We want to account for duplicated edges with a set-like map.
        edgeMap := map[Edge]bool{}

        for j := 0; j < m; j++ {
            var x, y, c int
            // x, y, c, make an undirected edge in a graph.
            fmt.Scanf("%v %v %v", &x, &y, &c)
            // Make the node indices zero-indexed.
            x, y = x-1, y-1
            edgeToY := Edge{x, y, c}
            edgeToX := Edge{y, x, c}
            // The graph is undirected, so add edge in both node positions. Also,
            // check that no such unique combination (from, to, cost) exists (so
            // to remove duplicate entries). If there's an edge between two nodes
            // with different cost, lets consider it a different edge.
            if _, ok := edgeMap[edgeToY]; !ok {
                nodes[x] = append(nodes[x], &edgeToY)
                edgeMap[edgeToY] = true
            }
            if _, ok := edgeMap[edgeToX]; !ok {
                nodes[y] = append(nodes[y], &edgeToX)
                edgeMap[edgeToX] = true
            }
        }

        // s: the starting position.
        var s int
        fmt.Scanf("%v", &s)
        // Dijkstra algorithm will return an array with the lowest possible
        // distances to each node from a starting node (and -1 if its unreachable)
        distances := dijkstra(nodes, s-1)

        for i := range distances {
            // Don't print the starting location distance
            if distances[i] != 0 {
                fmt.Printf("%v", distances[i])
                if i+1 < len(distances) {
                    fmt.Printf(" ")
                } else {
                    fmt.Printf("\n")
                }
            }
        }
    }
}