#include<bits/stdc++.h>

 int mp[][],dis[],vis[];

 using namespace std;

 int n;

 void dij(int s)

 {

     int i,j,k;

     for(i=; i<n; i++)

     {

         dis[i]=mp[s][i];

         vis[i]=;

     }

     vis[s]=;

     for(j=; j<n; j++)

     {

         int min1=1e9;

         for(i=; i<n; i++)

         {

             if(min1>dis[i]&&!vis[i])

             {

                 min1=dis[i];

                 k=i;

             }

         }

         vis[k]=;

         for(i=; i<n; i++)

         {

             if(!vis[i]&&mp[k][i]<1e9)

             {

                 dis[i]=min(dis[i],max(dis[k],mp[k][i]));

             }

         }

     }

 }

 int main()

 {

     int t,u,v,w,i,j;

     cin>>t;

     for(int co=; co<=t; co++)

     {

         int m;

         scanf("%d%d",&n,&m);

         for(i=; i<n; i++)

             for(j=; j<n; j++)

             {

                 if(i==j)

                     mp[i][j]=;

                 else

                     mp[i][j]=1e9;

             }

         while(m--)

         {

             scanf("%d%d%d",&u,&v,&w);

             if(mp[u][v]>w)

                 mp[u][v]=mp[v][u]=w;

         }

         int s;

         cin>>s;

         dij(s);

         printf("Case %d:\n",co);

         for(i=; i<n; i++)

         {

             if(dis[i]==1e9)

                 puts("Impossible");

             else

                 printf("%d\n",dis[i]);

         }

     }

     return ;

 }