#include<bits/stdc++.h>
using namespace std;
#define D(x) cout<<#x<<" = "<<x<<endl
#define inf 1e9
#define mx 500

int n, m, root, t, cs;

vector<int> edge[mx+5];
int par[mx+5], dis[mx+5], cost[mx+5][mx+5], vis[mx+5];


struct node
{
    int x, d;
}ND;

bool operator < (node A, node B)
{
    if(A.d < B.d) return false;
    return true;
}

int path(int x)
{
    if(x == root) return 0;
    int p, mn = -1;
    while(x != root)
    {
        p = par[x];
        if(p == -1) return -1;
        mn = max(mn, cost[p][x]);
        x = p;
    }
    return mn;
}

void print()
{
    for(int i= 0; i< n;i++)
    {
        int ck = path(i);
        if(ck == -1) printf("Impossible\n");
        else printf("%d\n",ck);
    }
}

void solve(int src)
{
    memset(vis, 0, sizeof vis);
    memset(par, -1, sizeof par);
    for(int i = 0;i< n;i++) dis[i] = inf;

    node u;
    par[src] = src;
    dis[src] = 0;

    u.x = src;
    u.d = dis[src];

    priority_queue<node> q;
    q.push(u);
    while(!q.empty())
    {
        u = q.top();
        vis[u.x] = 1;
        q.pop();

        for(int i= 0;i<edge[u.x].size();i++)
        {
            node v;
            v.x = edge[u.x][i];
            v.d = cost[u.x][v.x];
            if(!vis[v.x] && dis[v.x] > v.d)
            {
                par[v.x] = u.x;
                dis[v.x] = v.d;
                q.push(v);
            }
        }
    }
    print();

}

void init(int x)
{
    for(int i = 0;i<=x;i++)
    {
        for(int j = 0;j<=x ;j++)
            cost[i][j] = inf;
        edge[i].clear();
    }
}


int main()
{
    int u, v, w;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init(n);
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&w);
            edge[u].push_back(v);
            edge[v].push_back(u);

            cost[u][v] = min(cost[u][v], w);
            cost[v][u] = cost[u][v];
        }
        scanf("%d",&root);
        printf("Case %d:\n",++cs);
        solve(root);

    }
}