#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<string>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define Maxn 52

#define Maxm 100010

#define LL __int64

#define Abs(x) ((x)>0?(x):(-x))

#define lson(x) (x<<1)

#define rson(x) (x<<1|1)

#define inf 0x3f3f3f3f

#define Mod 1000000007

using namespace std;

int dis[Maxn][Maxn],p[Maxn],t[Maxn],ft[Maxn],dp[<<][Maxn][<<],n,m,k;

LL fast[Maxn];

void init()

{

    memset(dis,,sizeof(dis));

    memset(fast,,sizeof(fast));

    memset(dp,,sizeof(dp));

    memset(ft,,sizeof(ft));

}

void floyd()

{

    int i,j,k;

    for(k=;k<=n;k++){

        dis[k][k]=;

        for(i=;i<=n;i++){

            for(j=;j<=n;j++){

                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

            }

        }

    }

}

int check(int p)

{

    int temp=;

    for(int i=;i<=k;i++) if(fast[i]&(1LL<<p)) temp|=(<<(i-));

    return temp;

}

void Min(int &a,int b)

{

    a=a>b?b:a;

}

int solve()

{

    int i,j,r,ki,kj,fi,fj,N;

    N=(<<k)-;

    dp[][][]=;

    for(ki=;ki<=N;ki++){

        for(fi=;fi<=N;fi++) if((ki&fi)==ki){

            for(i=;i<=n;i++)if(dp[ki][i][fi]<inf){

                for(kj=;kj<=k;kj++) if((ki&(<<(kj-)))==){

                    int fast=check(p[kj]);

                    Min(dp[ki|(<<(kj-))][p[kj]][fast|fi|(<<(kj-))],dp[ki][i][fi]+dis[i][p[kj]]+(((fast|fi)&(<<(kj-)))?ft[kj]:t[kj]));

                }

                for(j=;j<=n;j++){

                    int fast=check(j);

                    if((fast&fi)!=fast)

                        Min(dp[ki][j][fast|fi],dp[ki][i][fi]+dis[i][j]);

                }

            }

        }

    }

    int ans=inf;

    for(i=;i<=N;i++){

        for(j=;j<=n;j++){

            ans=min(ans,dp[N][j][i]+dis[j][]);

        }

    }

    return ans;

}

int main()

{

    int i,j,u,v,val,x,c,Case=;

    int T;

    scanf("%d",&T);

    while(T--){

        init();

        scanf("%d%d%d",&n,&m,&k);

        for(i=;i<=m;i++){

            scanf("%d%d%d",&u,&v,&val);

            dis[u][v]=dis[v][u]=min(dis[u][v],val);

        }

        for(i=;i<=k;i++){

            scanf("%d%d%d%d",&p[i],&t[i],&ft[i],&c);

            while(c--){

                scanf("%d",&x);

                fast[i]|=(1LL<<x);

            }

        }

        floyd();

        printf("Case #%d: %d\n",++Case,solve());

    }

    return ;

}