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

#define ll           long long
#define pii          pair<ll,ll>
#define bug(a)       cerr << #a << " : " << a << endl;
#define FastRead     ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAX = 3e6+10;

vector<pii>adj[MAX],newG[MAX];
map<pii,int>vis;
int node;
ll dist[MAX];

struct Info
{
    ll d;
    int u,x;

    Info(){}
    Info(ll _d,int _u,int _x)
    {
        d = _d;
        u = _u;
        x = _x;
    }
};
bool operator<(const Info &x,const Info &y)
{
    return x.d >= y.d;
}
bool endd[MAX];
int en;
void DFS(int src,int x,int par)
{
    if(src == en)
        endd[node] = 1;
    vis[{src,x}] = node++;
    int u = vis[{src,x}];
    //cout << src << " " << x << " " << par << endl;
    for(int j=0;j<adj[src].size();j++)
    {
        int v = adj[src][j].first , w = adj[src][j].second;
        int newX = __gcd(x,w);

        if(x >= w)
        {
            if(!vis[{v,newX}] && v != par)
            {
                DFS(v,newX,u);
                v = vis[{v,newX}];
                newG[u].push_back({v,w});
                newG[v].push_back({u,w});
            }
//            else if(v != par)
//            {
//                v = vis[{v,newX}];
//                newG[u].push_back({v,w});
//                newG[v].push_back({u,w});
//            }
        }
    }
}
ll dijkstra(int src,int en,int x)
{
    priority_queue< Info > pq;
    fill(dist,dist+MAX,1e18);

    pq.push({0,src,x});
    dist[src] = 0;

    while(pq.size())
    {
        int u = pq.top().u;
        ll d = pq.top().d;
        pq.pop();
        //cout << u << " >>> " << d << endl;
        if(endd[u])
            return d;

        for(int j=0;j<newG[u].size();j++)
        {
            int v = newG[u][j].first , w = newG[u][j].second;

            if(dist[v] > dist[u]+w)
            {
                dist[v] = dist[u]+w;
                pq.push({dist[v],v,__gcd(x,w)});
            }
        }
    }
    return 1e18;
}
int main()
{
    FastRead

    int t,cas=1;

    cin >> t;

    while(t--)
    {
        int n,m,x,y,w;

        cin >> n >> m;

        for(int i=1;i<=n;i++)
            adj[i].clear() , newG[i].clear();

        while(m--)
        {
            cin >> x >> y >> w;
            adj[x].push_back({y,w});
            adj[y].push_back({x,w});
        }

        vis.clear();
        memset(endd,0,sizeof endd);
        node = 1;
        int st;

        cin >> st >> en >> x;

        DFS(st,x,-1);


        ll res = dijkstra(vis[{st,x}],en,x);

        if(res < 1e18)
            cout << "Case " << cas++ << ": " << res << endl;
        else
            cout << "Case " << cas++ << ": impossible" << endl;
    }
}