#include <set>
#include <utility>
#include <vector>
#include <iostream>

using namespace std;

struct node;

struct edge
{
    int weight;
    node* n;
    bool operator ==(const edge& e) const{
        return n == e.n;
    }
    edge(int w, node* nn) : weight(w), n(nn){}
};

struct node
{
    int id;
    int distance;
    vector<edge*> edges;

    bool operator <(const node& n) const
    {
        if (distance == n.distance)
        {
            return id < n.id;
        }
        else
        {
            return distance < n.distance;
        }
    }

    void add(edge* e){
        bool found = false;
        for(int i=0; i<edges.size(); i++){
            if(edges[i]->n == e->n){
                edges[i]->weight = min(edges[i]->weight, e->weight);
                found = true;
                break;
            }
        }

        if(!found)
            edges.push_back(e);
    }
    bool operator ==(const node& n) const{
        return id == n.id;

    }

    node(int _id, int _distance) : id(_id), distance(_distance)
    {
    }
};

vector<int> Dijkstra(vector<node*> graph, node* source)
{
    vector<int> result(graph.size(), -1);
    source->distance = 0;
    set<node> s;
    vector<bool> seen(graph.size(), false);

    for (int i = 0; i < source->edges.size(); i++)
    {
        seen[source->id] = true;
        source->edges[i]->n->distance = source->edges[i]->weight;
        s.insert(*source->edges[i]->n);
    }

    while (!s.empty())
    {
        node n = *s.begin();
        s.erase(s.begin());

        result[n.id] = n.distance;
        seen[n.id] = true;

        for (int i = 0; i < n.edges.size(); i++)
        {
            if (!seen[n.edges[i]->n->id] && s.find(*n.edges[i]->n) != s.end())
            {
                if (n.edges[i]->weight + n.distance < n.edges[i]->n->distance)
                {
                    s.erase(*n.edges[i]->n);
                    n.edges[i]->n->distance = n.edges[i]->weight + n.distance;
                    s.insert(*n.edges[i]->n);
                }
            }
            else if (!seen[n.edges[i]->n->id])
            {
                n.edges[i]->n->distance = n.edges[i]->weight + n.distance;
                s.insert(*n.edges[i]->n);
            }
        }
    }

    return result;
}

int main(){

    int t;
    cin >> t;
    for(int a0 = 0; a0<t; a0++){
        int n, m;
        cin >> n; cin >> m;
        vector<node*> graph(n);
        for(int i=0; i<n; i++){
            graph[i] = new node(i, -1);
        }

        for(int i=0; i<m; i++){
            int from, to, distance;
            cin >> from; cin >> to; cin >> distance;
            graph[from-1]->add(new edge(distance, graph[to-1]));
            graph[to-1]->add(new edge(distance, graph[from-1]));
        }
        int s;
        cin >> s;

        vector<int> d = Dijkstra(graph, graph[s-1]);

        for(int i=0; i<d.size(); i++){
            if(graph[s-1]->id == i)
                continue;
            cout << d[i] << " ";
        }

        cout << endl;
    }
    return 0;
}