//Country roads (LOJ 1002)
// Vector Implementation

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

int final_minimum=INT_MAX;
vector < vector < pair < int,int > > > adj;

void find_maximum_cost(vector<pair < int,int > >& path)
{
    int mx=INT_MIN;
    for (int i = 0; i < path.size(); i++)
        mx=max(mx,path[i].second);
    final_minimum=min(final_minimum,mx);
}

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

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

    vector<pair < int,int > > path;
    path.push_back(make_pair(src,0));
    q.push(path);

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

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

        for (int i = 0; i < adj[last].size(); i++)
        {
            if (isNotVisited(adj[last][i].first, path))
            {
                vector<pair < int,int > > newpath(path);
                newpath.push_back(make_pair(adj[last][i].first,adj[last][i].second));
                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;
        adj.resize(n);


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

            adj[a].push_back(make_pair(b,c));
            adj[b].push_back(make_pair(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++)
            adj[i].clear();
    }


    return 0;
}