#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<vector>

 using namespace std;

 #define inf 1<<30

 #define FILL(a,b) memset(a,b,sizeof(a))

 int dp[<<][<<][];//访问过的+收集的票+当前顶点

 int pos[],time[],f_time[],map[][];

 int Mask[];

 int n,m,k,ans;

 void floyd()

 {

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

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

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

                 if(map[i][k]!=inf&&map[k][j]!=inf&&map[i][k]+map[k][j]<map[i][j])

                     map[i][j]=map[i][k]+map[k][j];

 }

 void Get_Dp()

 {

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

         for(int j=; j<=(<<k); j++)

             for(int u=; u<=n; u++)dp[i][j][u]=inf;

     dp[][][]=;

     for(int state1=; state1<(<<k); state1++) {

         for(int state2=; state2<(<<k); state2++) {

             for(int u=; u<=n; u++)if(dp[state1][state2][u]<inf) {

                     for(int i=; i<k; i++)if(!(state1&(<<i))) {

                             int cost=map[u][pos[i]];

                             if(state2&(<<i))cost+=f_time[i];

                             else cost+=time[i];

                             dp[state1|(<<i)][state2|Mask[pos[i]]][pos[i]]=min(dp[state1|(<<i)][state2|Mask[pos[i]]][pos[i]],dp[state1][state2][u]+cost);

                         }

                     for(int v=; v<=n; v++) {

                         dp[state1][state2|Mask[v]][v]=min(dp[state1][state2|Mask[v]][v],dp[state1][state2][u]+map[u][v]);

                     }

                 }

         }

     }

     ans=inf;

     for(int state=;state<(<<k);state++){

         ans=min(ans,dp[(<<k)-][state][]);

     }

 }

 int main()

 {

     int _case,u,v,w,num,t=;

     scanf("%d",&_case);

     while(_case--) {

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

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

             for(int j=; j<=n; j++)map[i][j]=(i==j?:inf);

         while(m--) {

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

             map[u][v]=map[v][u]=min(map[u][v],w);

         }

         FILL(Mask,);

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

             scanf("%d%d%d%d",&pos[i],&time[i],&f_time[i],&num);

             while(num--) {

                 scanf("%d",&v);

                 Mask[v]|=(<<i);

             }

         }

         floyd();

         Get_Dp();

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

     }

     return ;

 }