#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define LL long long
#define FastRead ios_base::sync_with_stdio(0);cin.tie(0);
#define pii pair<int,int>
using namespace std;
struct edge
{
int u,v,w;
bool operator<(const edge& p) const
{
return w < p.w;
}
};
int par[505];
int vis[505];
int co[505];
vector<edge>e;
vector<int>tree[505];
map< pair<int,int> ,int >mp;
int find(int n)
{
if(n==par[n])return n;
return par[n]=find(par[n]);
}
int mst(int n)
{
sort(e.begin(),e.end());
int i,s=0,cnt=0,u,v;
for(i=0;i<=n;i++)par[i]=i;
for(i=0;i<e.size();i++)
{
u=find(e[i].u);
v=find(e[i].v);
if(u!=v)
{
par[u]=v;
cnt++;
tree[u].push_back(v);
tree[v].push_back(u);
if(u<v)swap(u,v);
mp[make_pair(u,v)]=e[i].w;
if(cnt==n-1)break;
}
}
}
int dfs(int node,int cost)
{
vis[node]=1;
int i,a,b,c;
for(i=0;i<tree[node].size();i++)
{
a=tree[node][i];
b=a;
c=node;
if(b<c)swap(b,c);
pii x=make_pair(b,c);
if(vis[a]==0)
{
co[a]=max(cost,mp[x]);
dfs(a,co[a]);
}
}
}
int main()
{
FastRead
int test,cs=0;
cin>>test;
while(test--)
{
memset(vis,0,sizeof(vis));
memset(co,0,sizeof(co));
memset(par,0,sizeof(par));
mp.clear();
int n,m,i,u,v,w,t;
for(i=0;i<505;i++)tree[i].clear();
e.clear();
cin>>n>>m;
edge get;
for(i=0;i<m;i++)
{
cin>>get.u>>get.v>>get.w;
e.push_back(get);
}
cin>>t;
mst(n);
dfs(t,0);
cout<<"Case "<<++cs<<":\n";
for(i=0;i<n;i++)
{
if(i==t)cout<<"0\n";
else if(co[i]==0)cout<<"Impossible\n";
else cout<<co[i]<<"\n";
}
}
}
CiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgaW5mIDB4M2YzZjNmM2YKI2RlZmluZSBMTCBsb25nIGxvbmcKI2RlZmluZSBGYXN0UmVhZCBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApO2Npbi50aWUoMCk7CiNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCBlZGdlCnsKICAgIGludCB1LHYsdzsKICAgIGJvb2wgb3BlcmF0b3I8KGNvbnN0IGVkZ2UmIHApIGNvbnN0CiAgICB7CiAgICAgICAgcmV0dXJuIHcgPCBwLnc7CiAgICB9Cn07CmludCBwYXJbNTA1XTsKaW50IHZpc1s1MDVdOwppbnQgY29bNTA1XTsKdmVjdG9yPGVkZ2U+ZTsKdmVjdG9yPGludD50cmVlWzUwNV07Cm1hcDwgcGFpcjxpbnQsaW50PiAsaW50ID5tcDsKaW50IGZpbmQoaW50IG4pCnsKICAgIGlmKG49PXBhcltuXSlyZXR1cm4gbjsKICAgIHJldHVybiBwYXJbbl09ZmluZChwYXJbbl0pOwp9CgppbnQgbXN0KGludCBuKQp7CiAgICBzb3J0KGUuYmVnaW4oKSxlLmVuZCgpKTsKICAgIGludCBpLHM9MCxjbnQ9MCx1LHY7CiAgICBmb3IoaT0wO2k8PW47aSsrKXBhcltpXT1pOwogICAgZm9yKGk9MDtpPGUuc2l6ZSgpO2krKykKICAgIHsKICAgICAgICB1PWZpbmQoZVtpXS51KTsKICAgICAgICB2PWZpbmQoZVtpXS52KTsKICAgICAgICBpZih1IT12KQogICAgICAgIHsKICAgICAgICAgICAgcGFyW3VdPXY7CiAgICAgICAgICAgIGNudCsrOwogICAgICAgICAgICB0cmVlW3VdLnB1c2hfYmFjayh2KTsKICAgICAgICAgICAgdHJlZVt2XS5wdXNoX2JhY2sodSk7CiAgICAgICAgICAgIGlmKHU8dilzd2FwKHUsdik7CiAgICAgICAgICAgIG1wW21ha2VfcGFpcih1LHYpXT1lW2ldLnc7CiAgICAgICAgICAgIGlmKGNudD09bi0xKWJyZWFrOwogICAgICAgIH0KICAgIH0KfQppbnQgZGZzKGludCBub2RlLGludCBjb3N0KQp7CiAgICB2aXNbbm9kZV09MTsKCiAgICBpbnQgaSxhLGIsYzsKICAgIGZvcihpPTA7aTx0cmVlW25vZGVdLnNpemUoKTtpKyspCiAgICB7CiAgICAgICAgYT10cmVlW25vZGVdW2ldOwogICAgICAgIGI9YTsKICAgICAgICBjPW5vZGU7CiAgICAgICAgaWYoYjxjKXN3YXAoYixjKTsKICAgICAgICBwaWkgeD1tYWtlX3BhaXIoYixjKTsKICAgICAgICBpZih2aXNbYV09PTApCiAgICAgICAgewogICAgICAgICAgICBjb1thXT1tYXgoY29zdCxtcFt4XSk7CiAgICAgICAgICAgIGRmcyhhLGNvW2FdKTsKICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKCkKewogICAgRmFzdFJlYWQKICAgIGludCB0ZXN0LGNzPTA7CiAgICBjaW4+PnRlc3Q7CiAgICB3aGlsZSh0ZXN0LS0pCiAgICB7CiAgICAgICAgbWVtc2V0KHZpcywwLHNpemVvZih2aXMpKTsKICAgICAgICBtZW1zZXQoY28sMCxzaXplb2YoY28pKTsKICAgICAgICBtZW1zZXQocGFyLDAsc2l6ZW9mKHBhcikpOwogICAgICAgIG1wLmNsZWFyKCk7CgogICAgICAgIGludCBuLG0saSx1LHYsdyx0OwogICAgICAgIGZvcihpPTA7aTw1MDU7aSsrKXRyZWVbaV0uY2xlYXIoKTsKICAgICAgICBlLmNsZWFyKCk7CgogICAgICAgIGNpbj4+bj4+bTsKICAgICAgICBlZGdlIGdldDsKICAgICAgICBmb3IoaT0wO2k8bTtpKyspCiAgICAgICAgewogICAgICAgICAgICBjaW4+PmdldC51Pj5nZXQudj4+Z2V0Lnc7CiAgICAgICAgICAgIGUucHVzaF9iYWNrKGdldCk7CgogICAgICAgIH0KICAgICAgICBjaW4+PnQ7CiAgICAgICAgbXN0KG4pOwogICAgICAgIGRmcyh0LDApOwogICAgICAgIGNvdXQ8PCJDYXNlICI8PCsrY3M8PCI6XG4iOwogICAgICAgIGZvcihpPTA7aTxuO2krKykKICAgICAgICB7CiAgICAgICAgICAgIGlmKGk9PXQpY291dDw8IjBcbiI7CiAgICAgICAgICAgIGVsc2UgaWYoY29baV09PTApY291dDw8IkltcG9zc2libGVcbiI7CiAgICAgICAgICAgIGVsc2UgY291dDw8Y29baV08PCJcbiI7CiAgICAgICAgfQogICAgfQp9Cg==