#include <bits/stdc++.h>
#define maxm 3001

using namespace std;

int t, n, m, u, v, c, s;
vector<pair<int, int> > G[maxm];

void shortestReach() {
    vector<int> D(n+1, INT_MAX);
    D[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > pq;
    pq.push(make_pair(0, s));
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        for(int i=0; i<G[u].size(); ++i){
            int v = G[u][i].first;
            int cost = G[u][i].second;
            if(D[v] > D[u] + cost){
                D[v] = D[u] + cost;
                pq.push(make_pair(D[v], v));
            }
        }
    }
    for(int i=1; i<=n; ++i)
        if(i != s)
            if(D[i] == INT_MAX)
                cout<<"-1 ";
            else
                cout<<D[i]<<" ";
    cout<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> t;
    while(t--){
        cin>>n>>m;
        for(int i=0; i<m; ++i){
            cin>>u>>v>>c;
            G[u].push_back(make_pair(v, c));
            G[v].push_back(make_pair(u, c));
        }
        cin>>s;
        shortestReach();
        for(int i=1; i<=n; ++i)
            G[i].clear();
    }
    return 0;
}