//Hints:Competitive programming books by Steven & Felix Halim
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz 123456
#define pii pair<int,int>
vector<pii>v[sz];
vector<pii>::iterator it;
int dist[sz]; //initializing distance of each node infinity
void dijkstra(int s){
priority_queue<pii, vector<pii>, greater<pii> >pq;
pq.push(make_pair(0,s)); //shorted in non-increasing order w.r.t distance so that the least distance can be pop out first
dist[s]=0;
while(!pq.empty()){
pii top=pq.top(); pq.pop();
int d=top.first; int u=top.second;
for(it=v[u].begin();it!=v[u].end();++it){
int v=it->first; int weight_u_v=it->second;
if(max(dist[u],weight_u_v)<dist[v]){
dist[v]=max(dist[u],weight_u_v);
pq.push(make_pair(dist[v],v));
}
}
}
}
int main()
{
int N,E,s,t,i,j,x,y,w,tc,cs=0;
scanf("%d",&tc);
while(tc--){
scanf("%d%d",&N,&E);
for(i=0;i<N;i++)dist[i]=inf;
for(i=0;i<E;i++){
scanf("%d%d%d",&x,&y,&w);
v[x].push_back(make_pair(y,w));
v[y].push_back(make_pair(x,w));
}
scanf("%d",&s);
dijkstra(s);
printf("Case %d:\n",++cs);
for(i=0;i<N;i++){
if(dist[i]==inf)printf("Impossible\n");
else printf("%d\n",dist[i]);
}
for(int f=0;f<N;f++)v[f].clear();
}
return 0;
}
/*
5 6
0 1 5
0 1 4
2 1 3
3 0 7
3 4 6
3 1 8
1
*/
Ly9IaW50czpDb21wZXRpdGl2ZSBwcm9ncmFtbWluZyBib29rcyBieSBTdGV2ZW4gJiBGZWxpeCBIYWxpbQojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGluZiAweDNmM2YzZjNmCiNkZWZpbmUgc3ogMTIzNDU2CiNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KdmVjdG9yPHBpaT52W3N6XTsKdmVjdG9yPHBpaT46Oml0ZXJhdG9yIGl0OwppbnQgZGlzdFtzel07ICAvL2luaXRpYWxpemluZyBkaXN0YW5jZSBvZiBlYWNoIG5vZGUgaW5maW5pdHkKCnZvaWQgZGlqa3N0cmEoaW50IHMpewogICAgcHJpb3JpdHlfcXVldWU8cGlpLCB2ZWN0b3I8cGlpPiwgZ3JlYXRlcjxwaWk+ID5wcTsKICAgIHBxLnB1c2gobWFrZV9wYWlyKDAscykpOyAgICAvL3Nob3J0ZWQgaW4gbm9uLWluY3JlYXNpbmcgb3JkZXIgdy5yLnQgZGlzdGFuY2Ugc28gdGhhdCB0aGUgbGVhc3QgZGlzdGFuY2UgY2FuIGJlIHBvcCBvdXQgZmlyc3QKICAgIGRpc3Rbc109MDsKICAgIHdoaWxlKCFwcS5lbXB0eSgpKXsKICAgICAgICBwaWkgdG9wPXBxLnRvcCgpOyBwcS5wb3AoKTsKICAgICAgICBpbnQgZD10b3AuZmlyc3Q7IGludCB1PXRvcC5zZWNvbmQ7CiAgICAgICAgICAgIGZvcihpdD12W3VdLmJlZ2luKCk7aXQhPXZbdV0uZW5kKCk7KytpdCl7CiAgICAgICAgICAgICAgICBpbnQgdj1pdC0+Zmlyc3Q7IGludCB3ZWlnaHRfdV92PWl0LT5zZWNvbmQ7CiAgICAgICAgICAgICAgICBpZihtYXgoZGlzdFt1XSx3ZWlnaHRfdV92KTxkaXN0W3ZdKXsKICAgICAgICAgICAgICAgICAgICBkaXN0W3ZdPW1heChkaXN0W3VdLHdlaWdodF91X3YpOwogICAgICAgICAgICAgICAgICAgIHBxLnB1c2gobWFrZV9wYWlyKGRpc3Rbdl0sdikpOwogICAgICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQppbnQgbWFpbigpCnsKICAgIGludCBOLEUscyx0LGksaix4LHksdyx0Yyxjcz0wOwogICAgc2NhbmYoIiVkIiwmdGMpOwogICAgd2hpbGUodGMtLSl7CiAgICBzY2FuZigiJWQlZCIsJk4sJkUpOwogICAgZm9yKGk9MDtpPE47aSsrKWRpc3RbaV09aW5mOwogICAgZm9yKGk9MDtpPEU7aSsrKXsKICAgICAgICBzY2FuZigiJWQlZCVkIiwmeCwmeSwmdyk7CiAgICAgICAgdlt4XS5wdXNoX2JhY2sobWFrZV9wYWlyKHksdykpOwogICAgICAgIHZbeV0ucHVzaF9iYWNrKG1ha2VfcGFpcih4LHcpKTsKICAgIH0KICAgIHNjYW5mKCIlZCIsJnMpOwogICAgZGlqa3N0cmEocyk7CiAgICBwcmludGYoIkNhc2UgJWQ6XG4iLCsrY3MpOwogICAgZm9yKGk9MDtpPE47aSsrKXsKICAgICAgICBpZihkaXN0W2ldPT1pbmYpcHJpbnRmKCJJbXBvc3NpYmxlXG4iKTsKICAgICAgICBlbHNlIHByaW50ZigiJWRcbiIsZGlzdFtpXSk7CiAgICB9CiAgICBmb3IoaW50IGY9MDtmPE47ZisrKXZbZl0uY2xlYXIoKTsKICAgIH0KICAgIHJldHVybiAwOwp9CgovKgo1IDYKMCAxIDUKMCAxIDQKMiAxIDMKMyAwIDcKMyA0IDYKMyAxIDgKMQoqLwo=