Untitled

package TuanTrangMat;

import java.util.Scanner;

public class test {
static int N,M,K;
static int[] DiemVs=new int[20];
static int[][] matrix=new int[1001][1001];
static int[][] mtk=new int[1001][1001];
static int[] index=new int[1001];
static int[][] ChiPhi=new int[1001][1001];
static int[] visit=new int[1001];
static int ans=0;
static int[] vs=new int[1001];
static void Dijkstra(int n) {
	for(int i=1;i<=N;i++) {
		ChiPhi[n][i]=999999;
		visit[i]=0;
	}
	ChiPhi[n][n]=0;
	int minPoint;
	int minVal;
	for(int i=1;i<=N;i++) {
		minPoint=-1;
		minVal=999999;
		for(int j=1;j<=N;j++) {
			if(visit[j]==0 && ChiPhi[n][j]<minVal) {
				minVal=ChiPhi[n][j];
				minPoint=j;
			}
		}
		visit[minPoint]=1;
		int tmp;
		for(int j=0;j<index[minPoint];j++) {
			tmp=minVal+matrix[minPoint][mtk[minPoint][j]];
			if(tmp<ChiPhi[n][mtk[minPoint][j]] && visit[mtk[minPoint][j]]==0) {
				ChiPhi[n][mtk[minPoint][j]]=tmp;
			}
		}
	}
}

static void Backtrack(int dinh,int soDiemCanDi,int chiphi) {
	if(soDiemCanDi==K) {
		if(ChiPhi[dinh][1]!=999999) {
			if(chiphi+ChiPhi[dinh][1]<ans) {
				ans=chiphi+ChiPhi[dinh][1];
			}
		}
		return;
	}
	if(chiphi>ans) {
		return;
	}
	for(int i=0;i<=K;i++) {
		if(vs[DiemVs[i]]==0 && ChiPhi[dinh][DiemVs[i]]!=999999) {
			vs[DiemVs[i]]=1;
			Backtrack(DiemVs[i], soDiemCanDi+1, chiphi+ChiPhi[dinh][DiemVs[i]]);
			vs[DiemVs[i]]=0;
		}
	}
}

public static void main(String[] args) {
	Scanner sc=new Scanner(System.in);
	int tc=sc.nextInt();
	for(int i=0;i<tc;i++) {
		N=sc.nextInt();
		M=sc.nextInt();
		K=sc.nextInt();
		for(int j=0;j<=N;j++) {
			DiemVs[j]=0;
			index[j]=0;
			vs[j]=0;
			for(int k=0;k<=N;k++) {
				matrix[j][k]=999999;
				mtk[j][k]=0;
			}
		}
		for(int j=1;j<=K;j++) {
			DiemVs[j]=sc.nextInt();
		}
		DiemVs[0]=1;
		for(int j=0;j<M;j++) {
			int r=sc.nextInt();
			int c=sc.nextInt();
			int money=sc.nextInt();
			matrix[r][c]=money;
			mtk[r][index[r]]=c;
			index[r]++;
		}
		for(int j=0;j<=K;j++) {
			Dijkstra(DiemVs[j]);
		}
		ans=999999;
		vs[1]=1;
		Backtrack(1, 0, 0);
		if(ans!=999999) {
			System.out.println("Case #"+(i+1));
			System.out.println(ans);
			System.out.println();
		}
		else {
			System.out.println("Case #"+(i+1));
			System.out.println(-1);
			System.out.println();
		}
		
		
	}
}
}