#include<bits/stdc++.h>
using namespace std;
class graph{
unordered_map<int,list<pair<int,int>>>l;
public:
void add(int a,int b,int w)
{
l[a].push_back(make_pair(b,w));
l[b].push_back(make_pair(a,w));
//l[a]=(make_pair(b,w));
//l[b]=(make_pair(a,w));
}
void solve(int src)
{
map<int,int> visited;
for(auto np:l)
{
visited[np.first]=INT_MAX;
}
set<pair<int,int>> s; // distance node
visited[src]=0;
pair<int,int> p=make_pair(0,src);
s.insert(p);
//s.push_back(p);
//s.insert(make_pair(0,src));
while(!s.empty())
{
auto p=*s.begin();
int node=p.second;
int d=p.first;
s.erase(s.begin());
for(auto nbr:l[node])
{
if(d+nbr.second<visited[nbr.first])
{
// means this is the shortest distance
// so update the node in the set ;
int cnode=nbr.first;
auto f=s.find(make_pair(visited[nbr.first],cnode));
if(f!=s.end())
{
s.erase(f);
}
visited[nbr.first]=d+nbr.second;
s.insert(make_pair(d+nbr.second,cnode));
}
}
}
// cout<<"heloo ";
for(auto x:visited)
{
if(x.first!=src)
{
if(x.second==INT_MAX)
{
cout<<-1<<" ";
}
else
{
cout<<x.second<<" ";
}
}
}
}
};
int main()
{
int t;
cin>>t;
while(t–)
{
graph g;
int n,m;
cin>>n>>m;
// now we have to add edjes
while(m–)
{
int a,b,w;
cin>>a>>b>>w;
g.add(a,b,w);
}
int src;
cin>>src;
g.solve(src);
// now make the dijkarstra func
}
}