Untitled

package tuan_trang_mat;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, m, k, check;
	static long res;
	static int[][] a;
	static int[] vitri, visit, comb, visithv, parent;
	static long[][] kc;

	static void cal_distan() {
		kc = new long[n + 1][n + 1];

		for (int i = 0; i <= k; i++) {
			int[] q = new int[10000];
			long[][] lan = new long[n + 1][n + 1];
			int front = 0, rear = 1;
			q[front] = vitri[i];
			visit = new int[n + 1];
			visit[vitri[i]] = 1;
			parent = new int[n+1];
			while (front < rear) {
				int x = q[front];
				visit[x] = 2;
				for (int j = 1; j <= n; j++) {
					if (a[x][j] > 0 && visit[j] == 0) {
						q[rear] = j;
						rear++;
						lan[vitri[i]][j] = lan[vitri[i]][x] +  a[x][j];
						visit[j] = 1;
					}else
					if (a[x][j] > 0 && visit[j] == 1 && lan[vitri[i]][j] > lan[vitri[i]][x] +  a[x][j]) {
						lan[vitri[i]][j] = lan[vitri[i]][x] +  a[x][j];
				
					}else
						if (a[x][j] > 0 && visit[j] == 2 && lan[vitri[i]][j] > lan[vitri[i]][x] +  a[x][j]) {
							q[rear] = j;
							rear++;
							lan[vitri[i]][j] = lan[vitri[i]][x] +  a[x][j];
						}
				}
				front++;
			}
			for (int j = 1; j <= n; j++) {
				kc[vitri[i]][j] = lan[vitri[i]][j];
			}
		}
	}
	
	static void backtrack(int count, long chiphi){
		if(count == k +1 ){
			
//			for(int i = 0; i <=k ; i++){
//				System.out.print(comb[i] + " ");
//			}
//			System.out.println();
			long x = chiphi + kc[comb[count-1]][1];
//			System.out.println("k " + count + " " + kc[comb[count-1]][1]);
//			for(int i = 1; i <= k;i++)
			if(x < res) {
//				check =1;
				res = x;
			}
			return;
		}
		if(chiphi >= res){
			return;
		}
		
		for(int i = 1; i <= k ; i++){
			if(visithv[i] == 0){
				visithv[i] = 1;
				comb[count] = vitri[i];
				if(kc[comb[count-1]][comb[count]] == 0){
					check = 0;
					return;
				}
//				System.out.println((count +1) + " kc " + kc[comb[count-1]][comb[count]]);
				backtrack(count +1 , chiphi + kc[comb[count-1]][comb[count]]);
				visithv[i] = 0;
			}
		}
	}

	public static void main(String[] args) {
		
		try {
			System.setIn(new FileInputStream("input(ttm).txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			m = scanner.nextInt();
			k = scanner.nextInt();
			vitri = new int[k+1];
			vitri[0] = 1;
			for (int i = 1; i <= k; i++) {
				vitri[i] = scanner.nextInt();
			}
			a = new int[n + 1][n + 1];
			for (int i = 0; i < m; i++) {
				a[scanner.nextInt()][scanner.nextInt()] = scanner.nextInt();
			}
			
//			for (int i = 0; i <= k; i++) {
//				System.out.print(vitri[i] + " ");
//			}
//			System.out.println();
			
			check = 1;
			res = Long.MAX_VALUE;
			
			
			cal_distan();
//			for(int i = 1; i <=n;i++){
//				for(int j=1;j<=n;j++){
//					System.out.print(kc[i][j] + " ");
//				}
//				System.out.println();
//			}
			
			visithv = new int[k+1];
			comb = new int[k+1];
			comb[0] = 1;
			
			backtrack(1, 0);
			if(check == 0){
				System.out.println("Case #" + t + "\n-1\n" );
			}else{
				System.out.println("Case #" + t + "\n" + res+"\n");
			}
		}
		scanner.close();
	}
}