#include
#include<bits/stdc++.h>
using namespace std;
void addEdge(vector<pair<int,int>>adj[],int u,int v,int data){
adj[u].push_back(make_pair(v,data));
adj[v].push_back(make_pair(u,data));
}
void printGraph(vector<pair<int,int>>adj[],int v){
for(int i=0;i<v;i++){
for(auto x:adj[i]){
cout<<x.first<<x.second<<" “;
}
cout<<”\n";
}
}
void diskstra(vector<pair<int,int>>adj[],int v,int s){
unordered_map<int,int>dist;
for(int i=0;i<v;i++){
dist[i]=INT_MAX;
}
dist[s]=0;
set<pair<int,int>>d;
d.insert(make_pair(0,s));
while(!d.empty()){
auto e=*(d.begin());
int p=e.first;
int q=e.second;
d.erase(d.begin());
for(auto w:adj[q]){
if(dist[w.first]>p+w.second){
auto f=d.find(make_pair(dist[w.first],w.first));
if(f!=d.end()){
d.erase(f);
}
dist[w.first]=p+w.second;
d.insert(make_pair(dist[w.first],w.first));
}
}
}
for(int i=0;i<v;i++) {
if(i!=s){
cout<<dist[i]<<" ";}
}
}
int main(){
int n;
cin>>n;
for(int k=0;k<n;k++){
int v;
cin>>v;
int e;
cin>>e;
vector<pair<int,int>>adj[v];
for(int i=0;i<e;i++){
int a,b,c;
cin>>a>>b>>c;
addEdge(adj, a-1, b-1,c);
}
int s;
cin>>s;
diskstra(adj,v,s-1);
cout<<"\n" ;
}
}