//Country Roads (LOJ 1002)
// Array implementation

#include <bits/stdc++.h>
using namespace std;

int final_minimum=INT_MAX;
int adj[505][505];

void find_maximum_cost(vector <int>& path)
{
    int mx=INT_MIN;
    //cout<<path[0]<<" ";

    for (int i = 1; i < path.size(); i++)
    {
        mx=max(mx,adj[path[i]][path[i-1]]);
        //cout<<adj[path[i]][path[i-1]]<<" ";
    }
    //cout<<endl;

    final_minimum=min(final_minimum,mx);
}

int isNotVisited(int x, vector <int>& path)
{
    int size = path.size();
    for (int i = 0; i < size; i++)
        if (path[i] == x)
            return 0;
    return 1;
}

void findpaths(int src,int dst,int n)
{
    queue< vector <int> > q;

    vector <int> path;
    path.push_back(src);
    q.push(path);

    while (!q.empty()) {
        path = q.front();
        q.pop();
        int last = path[path.size() - 1];

        if (last == dst)
            find_maximum_cost(path);

        for (int i = 0; i < n; i++)
        {
            if ( adj[last][i] && isNotVisited(i, path))
            {
                vector <int> newpath(path);
                newpath.push_back(i);
                q.push(newpath);
            }
        }
    }
}


int main()
{
    int test_case;
    cin>>test_case;

    for (int t=1;t<=test_case;t++)
    {
        int n,m;
        cin>>n>>m;

        for (int i=0;i<=n;i++)
            for (int j=0;j<=n;j++)
                adj[i][j]=0;

        for (int i=0;i<m;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;

            if (adj[a][b]==0) adj[a][b]=c;
            else adj[a][b]=min(adj[a][b],c);
            if (adj[b][a]==0) adj[b][a]=c;
            else adj[b][a]=min(adj[b][a],c);
        }

        int src;
        cin>>src;

        cout<<"Case "<<t<<":"<<endl;

        for (int i=0;i<n;i++)
        {
            if (i==src) {cout<<0<<endl;continue;}
            findpaths(src, i, n);
            if (final_minimum==INT_MAX) {cout<<"Impossible"<<endl;continue;}
            cout<<final_minimum<<endl;
            final_minimum=INT_MAX;
        }


        /*for (int i=0;i<n;i++)
        {
            for (int j=0;j<n;j++)
                cout<<adj[i][j]<<" ";
            cout<<endl;
        }*/


    }


    return 0;
}