Senior Pan fails in his discrete math exam again. So he asks Master ZKC to give him graph theory problems everyday.
The task is simple : ZKC will give Pan a directed graph every time, and selects some nodes from that graph, you can calculate the minimum distance of every pair of nodes chosen in these nodes and now ZKC only cares about the minimum among them. That is still too hard for poor Pan, so he asks you for help.

 

The first line contains one integer T, represents the number of Test Cases.1≤T≤5.Then T Test Cases, for each Test Cases, the first line contains two integers n,m representing the number of nodes and the number of edges.1≤n,m≤100000
Then m lines follow. Each line contains three integers xi,yi representing an edge, and vi representing its length.1≤xi,yi≤n,1≤vi≤100000
Then one line contains one integer K, the number of nodes that Master Dong selects out.1≤K≤n
The following line contains K unique integers ai, the nodes that Master Dong selects out.1≤ai≤n,ai!=aj

 

For every Test Case, output one integer: the answer

 

 

 /*有向图，给出询问集合，求出集合中的点，两两之间的最短距离

 因为边权都是正的，所以用的Dijkstra算法求最短路

 开一个超源0，用长度为0的边连接到各个起点，在把每个终点用长度为0的边连接到超汇n+1

 这样0到n+1的最短路就是从所有的起点到所有的终点路径中最短的

 所以要想办法把真正的最短答案的起点分到起点集合，最优终点放到终点集合，

 然后起点终点互换，再做一次即可。

 */

 #include <stdio.h>

 #include <algorithm>

 #include <iostream>

 #include <queue>

 using namespace std;

 #define N 100010

 #define INF 0x3f3f3f3f3f3f3f3fLL

 #define LL long long

 #define p E[i].x

 #define bit(x) (1<<(x))

 using namespace std;

 struct node{

     int x;

     LL v;

     bool operator<(const node &tmp)const{       //定义结构体，sort时按v大的优先。

         return v>tmp.v;

     }

 };

 priority_queue<node> q;  

 struct edge{      //结构体

     int x,to,v;

 }E[N<<];

 int n,m,totE,g[N],X[N],Y[N],Z[N],a[N];

 LL dist[N];

 bool v[N];

 void addedge(int x,int y,int v){ //存边

     E[++totE] = (edge){y,g[x],v}; g[x] = totE;

 }

 LL calc_dist(int S,int T){    //迪杰斯特拉算法

     for(int i=;i<=n+;i++) dist[i] = INF, v[i] = ;

     dist[S]=;

     q.push((node){S,});

     node tmp;

     while(!q.empty()){

         tmp = q.top(); q.pop();

         int x = tmp.x;

         if(v[x]) continue;

         v[x] = ;

         for(int i=g[x];i;i=E[i].to)

         if(!v[p] && dist[p]>dist[x]+E[i].v){

                 dist[p] = dist[x] + E[i].v;

                 q.push((node){p,dist[p]});

         }

     }

     return dist[T];

 }

 int main(){

     //freopen("in0.txt","r",stdin);

     int T,K,Te = ;

     cin>>T;

     while(T--){

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

         for(int i=;i<=m;i++) scanf("%d%d%d",&X[i],&Y[i],&Z[i]);

         scanf("%d",&K);

         for(int i=;i<=K;i++) scanf("%d",&a[i]);

         LL ans = INF;

         for(int t=;t<;t++){    //将点分成两个集合，一部分为起点，一部分为终点。二进制位数最大为17位，这里取的20，肯定可以。

             totE = ;

         for(int i=;i<=n+;i++) g[i] = ;

         for(int i=;i<=m;i++) addedge(X[i],Y[i],Z[i]);

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

             if(a[i]&bit(t)) addedge(,a[i],);//将这些点作为起点集合和源点相连，边权为0

             else addedge(a[i],n+,);//终点集合与汇点相连，边权为0

         }

         ans = min(ans, calc_dist(,n+));

             totE = ;

         for(int i=;i<=n+;i++) g[i] = ;

         for(int i=;i<=m;i++) addedge(X[i],Y[i],Z[i]);

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

             if((a[i]&bit(t))==) addedge(,a[i],);//和上边差不多，只是这次作为终点集合与汇点相连

             else addedge(a[i],n+,);//起点集合与源点相连

         }

             ans = min(ans, calc_dist(,n+));   //结果为最短路

         }

         //assert( ans < INF );

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

     }

     return ;

 }

 /*迪杰斯特拉算法，运用贪心的算法模式，求解最短路。

 算法解决的是有向图中单个源点到其他顶点的最短路径问题

 主要特点是每次迭代时选择的下一个顶点是标记点之外的距离源点最近的顶点

 */