#include<bits/stdc++.h>
using namespace std;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<int> > vvi;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define DEC(i,a,b) for(int i=(a); i>=b; --i)
#define FORV(v,i) for( int i=0;i<(int)v.size();++i)
#define FORD(v,i) for(int i=v.size()-1;i>=0;--i)
#define all(c) (c).begin(),(c).end()
#define sz(c) int((c).size())
#define pb push_back
#define ull unsigned long long
#define ll long long
#define MOD 1000000007ULL
typedef vector<vector<pair<int,int> > > Graph;
class Comparator
{
public:
int operator() ( const pair<int,int>& p1, const pair<int,int> &p2)
{
return p1.second>p2.second;
}
};
void dijkstra(const Graph &G,const int &S,vector<int> &d)
{
d.resize(G.size(),INT_MAX);
priority_queue<pair<int,int>, vector<pair<int,int> >, Comparator> Q;
d[S] = 0;
Q.push(make_pair(S,d[S]));
while(!Q.empty())
{
int u = Q.top().first;
Q.pop();
for(unsigned int i=0; i < G[u].size(); i++)
{
int v = G[u][i].first;
int w = G[u][i].second;
if(d[v] > d[u]+w)
{
d[v] = d[u]+w;
Q.push(make_pair(v,d[v]));
}
}
}
}
int main()
{
int t;
ios_base::sync_with_stdio(false);
cin>>t;
stringstream ss;
FOR(i,0,t)
{
int n,m;
cin>>n>>m;
Graph V(n);
FOR(j,0,m)
{
int x,y,w;
cin>>x>>y>>w;
x--;
y--;
V[x].push_back(make_pair(y,w));
V[y].push_back(make_pair(x,w));
}
int S;
cin>>S;
S--;
vector<int> d;
dijkstra(V,S,d);
FORV(d,j)
{
if(j!=S)
{
if(d[j] == INT_MAX)
ss<<-1<<" ";
else
ss<<d[j]<<" ";
}
}
ss<<"\n";
}
cout<<ss.str();
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiB2ZWN0b3I8c3RyaW5nPiB2czsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiB2ZWN0b3I8bG9uZyBsb25nPiB2bGw7CnR5cGVkZWYgdmVjdG9yPHZlY3RvcjxpbnQ+ID4gdnZpOwojZGVmaW5lIEZPUihpLGEsYikgZm9yKGludCBpPShhKTtpPChiKTsrK2kpCiNkZWZpbmUgREVDKGksYSxiKSBmb3IoaW50IGk9KGEpOyBpPj1iOyAtLWkpCiNkZWZpbmUgRk9SVih2LGkpIGZvciggaW50IGk9MDtpPChpbnQpdi5zaXplKCk7KytpKQojZGVmaW5lIEZPUkQodixpKSBmb3IoaW50IGk9di5zaXplKCktMTtpPj0wOy0taSkKI2RlZmluZSBhbGwoYykgKGMpLmJlZ2luKCksKGMpLmVuZCgpCiNkZWZpbmUgc3ooYykgaW50KChjKS5zaXplKCkpCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgdWxsIHVuc2lnbmVkIGxvbmcgbG9uZwojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIE1PRCAxMDAwMDAwMDA3VUxMCgoKdHlwZWRlZiB2ZWN0b3I8dmVjdG9yPHBhaXI8aW50LGludD4gPiA+IEdyYXBoOwpjbGFzcyBDb21wYXJhdG9yCnsKCXB1YmxpYzoKIAlpbnQgb3BlcmF0b3IoKSAoIGNvbnN0IHBhaXI8aW50LGludD4mIHAxLCBjb25zdCBwYWlyPGludCxpbnQ+ICZwMikKIAl7CiAJCXJldHVybiBwMS5zZWNvbmQ+cDIuc2Vjb25kOwogCX0KfTsKCgp2b2lkIGRpamtzdHJhKGNvbnN0IEdyYXBoICZHLGNvbnN0IGludCAmUyx2ZWN0b3I8aW50PiAmZCkKewoJZC5yZXNpemUoRy5zaXplKCksSU5UX01BWCk7Cglwcmlvcml0eV9xdWV1ZTxwYWlyPGludCxpbnQ+LCB2ZWN0b3I8cGFpcjxpbnQsaW50PiA+LCBDb21wYXJhdG9yPiBROwoJZFtTXSA9IDA7CglRLnB1c2gobWFrZV9wYWlyKFMsZFtTXSkpOwoJd2hpbGUoIVEuZW1wdHkoKSkKCXsKCQlpbnQgdSA9IFEudG9wKCkuZmlyc3Q7CgkJUS5wb3AoKTsKCQlmb3IodW5zaWduZWQgaW50IGk9MDsgaSA8IEdbdV0uc2l6ZSgpOyBpKyspCgkJewoJCQlpbnQgdiA9IEdbdV1baV0uZmlyc3Q7CgkJCWludCB3ID0gR1t1XVtpXS5zZWNvbmQ7CgkJCWlmKGRbdl0gPiBkW3VdK3cpCgkJCXsKCSAgIAkJCWRbdl0gPSBkW3VdK3c7CgkgICAJCQlRLnB1c2gobWFrZV9wYWlyKHYsZFt2XSkpOwoJICAJCX0KCSAJfQoJfQp9CgppbnQgbWFpbigpCnsKCWludCB0OwoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgljaW4+PnQ7CglzdHJpbmdzdHJlYW0gc3M7CglGT1IoaSwwLHQpCgl7CgkJaW50IG4sbTsKCQljaW4+Pm4+Pm07CgkJR3JhcGggVihuKTsKCQlGT1IoaiwwLG0pCgkJewoJCQlpbnQgeCx5LHc7CgkJCWNpbj4+eD4+eT4+dzsKCQkJeC0tOwoJCQl5LS07CgkJCVZbeF0ucHVzaF9iYWNrKG1ha2VfcGFpcih5LHcpKTsKCQkJVlt5XS5wdXNoX2JhY2sobWFrZV9wYWlyKHgsdykpOwoJCX0KCQlpbnQgUzsKCQljaW4+PlM7CgkJUy0tOwoJCXZlY3RvcjxpbnQ+IGQ7CgkJZGlqa3N0cmEoVixTLGQpOwoJCUZPUlYoZCxqKQoJCXsKCQkJaWYoaiE9UykKCQkJewoJCQkJaWYoZFtqXSA9PSBJTlRfTUFYKQoJCQkJCXNzPDwtMTw8IiAiOwoJCQkJZWxzZQoJCQkJCXNzPDxkW2pdPDwiICI7CgkJCX0KCQl9CgkJc3M8PCJcbiI7Cgl9Cgljb3V0PDxzcy5zdHIoKTsKCXJldHVybiAwOwp9Cg==