#include<bits/stdc++.h>
using namespace std;
template
class graph{
int v;
unordered_map<T,list<pair<int,T>>> l;
public:
graph(int v){
this->v=v;
}
void addedge(int x,int y,int r){
l[x].push_back({y,r});
l[y].push_back({x,r});
}
void printgraph(){
for(auto x:l){
T key=x.first;
list<pair<int,T>> value=x.second;
for(auto val:value){
cout<<key<<"---->"<<val.first<<","<<val.second<<endl;
}
// cout<<key<<----><<value.first<<","<<value.second;
}
}
unordered_map<T,int>dist;
void dijkstra(T src){
// int dist[v];
// unordered_map<T,int>dist;
for(auto j:l){
dist[j.first]=INT_MAX;
}
dist[src]=0;
set<pair<int,T>>s;
s.insert({0,src});
while(!s.empty()){
auto node=*(s.begin());
// s.erase(node);
int dis=node.first;
T u=node.second;
s.erase(s.begin());
for(auto x:l[u]){
auto v1=x.first;
// 1auto v1=v.second;
// cout<<v1<<endl;
int wt=x.second;
if(dist[u]+wt<dist[v1]){
auto f=s.find({dist[v1],v1});
if(f!=s.end()){
s.erase(f);
}
dist[v1]=dist[u]+wt;
s.insert({dist[v1],v1});
}
}
}
}
void print(T src){
for(auto x:dist){
if(x.second==INT_MAX){
cout<<"-1"<<" ";
}
else if(x.first!=src){
cout<<x.second<<" ";
}
}
}
};
int main() {
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
int x,y,r;
graph g(n);
while(m–){
cin>>x>>y>>r;
g.addedge(x,y,r);
}
int src;
cin>>src;
g.dijkstra(src);
g.print(src);
}
return 0;
}