loj 1281

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define infl 100000000000000018
ll n,m,p,a,b,c,e,f,g,h,x,mn;
struct edge
{
    ll node,cost;
    ll pro;
    bool operator<(const edge &p)const
    {
        if(cost==p.cost)return pro>p.pro;
        return cost>p.cost;
    }
};
vector<edge>v[10005];
ll d[10005][12];
//ll pr[10005];
void dijkstra()
{
    for(ll i=0;i<n;++i)
    {
        for(ll j=0;j<=10;j++)
        {
            d[i][j]=infl;
        }
    }
    d[0][0]=0;
    priority_queue<edge>q;
    edge u,w;
    u={0,0,0};
    q.push(u);
    while(!q.empty())
    {
        u=q.top();
        q.pop();
        a=u.node;
        b=u.cost;
        c=u.pro;
        for(ll i=0;i<v[a].size();++i)
        {
            f=v[a][i].node;
            g=v[a][i].cost;
            h=v[a][i].pro;
            x=c+h;
            if((d[a][c] + g <d[f][x]) && x<=e)
            {
                d[f][x]=d[a][c]+g;

                w={f,d[f][x],x};
                q.push(w);
            }
        }
    }
    mn=infl;
    for(ll i=0;i<=e;++i){
        //cout<<d[n-1][i]<<" ";
        mn=min(d[n-1][i],mn);

    }
}
int main()
{
    ll t,tc;
    scanf("%lld",&t);
    for(tc=1;tc<=t;++tc)
    {
        scanf("%lld %lld %lld %lld",&n,&m,&p,&e);
        for(ll i=0;i<m;++i){
            scanf("%lld %lld %lld",&a,&b,&c);
            edge temp;
            temp={b,c,0};
            v[a].pb(temp);
            //temp={b,c,0};
            //v[a].pb(temp);

        }
        for(ll i=0;i<p;++i){
            scanf("%lld %lld %lld",&a,&b,&c);
            edge temp;
            //temp={a,c,1};
            //v[b].pb(temp);
            temp={b,c,1};
            v[a].pb(temp);

        }
        dijkstra();
        printf("Case %d: ",tc);
        if(mn==infl)printf("Impossible\n");
        else printf("%lld\n",mn);
        for(ll i=0;i<n;++i)v[i].clear();
    }
    return  0;
}