#include<bits/stdc++.h>
using namespace std;

void algo(int s, vector<vector<pair<int, int> > > adj, vector<bool> &visited, vector<int> &dist, int n){
  visited[s] = true;
  dist[s] = 0;
  queue<int> q;
  q.push(s);
  while(!q.empty()){
    //cout << "inside" << endl;
    int temp = q.front();
    q.pop();
    vector<pair<int, int> >::iterator i;
    int u = -1, min_dist = INT_MAX;
    for(i = adj[temp].begin(); i != adj[temp].end(); i++){
      if(dist[(i->first)] > dist[temp] + i->second){
        dist[(i->first)] = dist[temp] + i->second;
      }
      // if(!visited[(i->first)] && dist[(i->first)] < min_dist){
      //   min_dist = dist[(i->first)];
      //   u = (i->first);
      //   q.push(u);
      //   visited[u] = true;
      // }
      for(int j = 1; j <= n; j++){
        if(!visited[j] && dist[j] < min_dist){
          min_dist = dist[j];
          u = j;
        }
      }
      if(u != -1){
        q.push(u);
        visited[u] = true;
      }
    }
  }
}

int main(){
  int t;
  cin >> t;
  while(t--){
    int n, m, u, v, w, s;
    cin >> n >> m;
    vector<vector<pair<int, int> > > adj(n+1, vector<pair<int, int> >());
    for(int i = 0; i < m; i++){
      cin >> u >> v >> w;
      adj[u].push_back(make_pair(v, w));
      adj[v].push_back(make_pair(u, w));
    }
    cin >> s;
    vector<int> dist(n+1, INT_MAX);
    vector<bool> visited(n+1, false);
    algo(s, adj, visited, dist, n);
    for(int i = 1; i <= n; i++){
      if(i != s && dist[i] != INT_MAX){
        cout << dist[i] << " ";
      }
      else if(i != s && dist[i] == INT_MAX){
        cout << -1 << " ";
      }
    }
    cout << endl;
  }
}