#include<iostream>
    #include<bits/stdc++.h>

    using namespace std;

    #define mx 520
    vector<int> g[mx],cost[mx],subgraph[mx],cost_sub[mx];

    struct node
    {
        int u,v;
        long long int w;
        node(int a,int c,long long int b){u=a,v=c; w=b;}
        bool operator > ( const node& p ) const { return w > p.w;}
    };

    bool visited[mx];

    long long int MST_primes(int src,int max_node)
    {
        for(int i=0;i<=max_node;i++)
        {
            subgraph[i].clear();
            cost_sub[i].clear();
        }

        long long int total_cost=0,p;
        memset(visited,false,sizeof(visited));
        priority_queue <node,vector<node>, greater<node> > q;
       // Vartex.push_back(src);
       int u;
        for(int i=1;i<max_node;i++)
        {
            if(visited[src]==false){
                      //cout<<34<<endl;
                 u=i;
                visited[src]=true;
                for(int j=0;j<g[src].size();j++)
                {
                    q.push(node(src,g[src][j],cost[src][j]));
                }
             // cout<<34<<endl;
                do
                {
                    if(q.empty())
                        break;
                    node top = q.top();
                    src = top.v;
                    u = top.u;
                    p = top.w;
                   // cout<<u<<" "<<src<<" "<<p<<endl;
                    q.pop();
                } while(visited[src]==true && !q.empty());



               if(visited[src]==false){
                    //cout<<u<< " "<<src<<endl;

                visited[u]=true;
                subgraph[u].push_back(src);
                subgraph[src].push_back(u);
                cost_sub[u].push_back(p);
                cost_sub[src].push_back(p);
               }

               // Vartex.push_back(src);

               // cout<<src<<endl;

                total_cost+=p;

        }


        }
        return total_cost;
    }


    int bfs(int n,int src)
    {
        queue<int>Q;
        Q.push(src);
        int visited[mx]={0};
        int d[mx];
       for(int i=0;i<=n;i++)
            d[i]=INT_MAX;
        //cout<<d[2]<<endl;
        d[src]=0;
        while(!Q.empty())
        {
            int u=Q.front();
            for(int i=0;i<subgraph[u].size();i++)
            {
                int v=subgraph[u][i];
                int cc = max(d[u],cost_sub[u][i]);
                if(d[v]>cc)
                {
                    //cout<<minimum[u]<<" "<<cost_sub[u][i]<<endl;
                    d[v]=cc;
                   // visited[v]=true;
                    Q.push(v);
                }
            }
            Q.pop();
        }
        for(int i=0;i<n;i++)
        {
            if(d[i]==INT_MAX)
                printf("Impossible\n");
            else
                printf("%d\n",d[i]);
        }
        return 0;
    }


    int main()
    {
    //    Vartex.clear();

        //freopen("in.txt","r",stdin);

        int u,v,w,n,e,test,des;
        cin>>test;
        for(int Case = 1; Case<=test ; Case++)
        {
            scanf("%d %d",&n,&e);
            for(int i=0;i<=n;i++)
            {
                g[i].clear();
                cost[i].clear();
            }

            for(int i=0;i<e;i++)
            {
                scanf("%d %d %d",&u,&v,&w);
                g[u].push_back(v);
                g[v].push_back(u);
                cost[u].push_back(w);
                cost[v].push_back(w);

            }
           /* for(int i=0;i<n;i++)
            {
                //cout<<i<<" : ";
                for(int j=0;j<g[i].size();j++)
                    cout<<i<<" ->> "<<g[i][j]<<"-->>"<<cost[i][j]<<endl;
                cout<<endl;
            }*/

            scanf("%d",&des);
            //cout<<"MST"<<endl;
            MST_primes(des,n);

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

        }



        return 0;
    }