#include <bits/stdc++.h>
#define maxm 3001
#define INF 999999999
using namespace std;

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

void shortestReach() {
    vector<int> D(n+1, INF);
    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()){
        pair<int, int> x = pq.top();
        int u = x.second;
        int d = x.first;
        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 + cost){
                D[v] = d + cost;
                pq.push(make_pair(D[v], v));
            }
        }
    }
    for(int i=1; i<D.size(); ++i)
        if(D[i] == INF)
            cout<<"-1 ";
        else if(i != s)
            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;
}