Untitled

#include <iostream>
#define MAXN 1001
#define INF 10000000

using namespace std;

int mtke[MAXN][MAXN];
int visit[MAXN];
int dske[MAXN][MAXN], index[MAXN];
int pay[MAXN][MAXN];
int N, M, K; //so dia diem - so tuyen duong - so diem can qua
int needVS[MAXN];
int mark[MAXN];
int ans;

void input()
{
	cin >> N >> M >> K;
	for(int i = 0; i <= N; i++){
		needVS[i] = 0;
		index[i] = 0;
		//visit[i] = 0;
		mark[i] = 0;
		for(int j = 0; j <= N; j++){
			mtke[i][j] = INF;
			dske[i][j] = 0;
			//pay[i][j] = 0;
		}
	}

	int a, b, c;
	for(int i = 1; i <= K; i++){
		cin >> needVS[i];
	}
	needVS[0] = 1;

	for(int i = 0; i < M; i++){
		cin >> a >> b >> c;
		dske[a][index[a]] = b;
		index[a]++;
		mtke[a][b] = c;
	}
	 
}

void dijkstra(int n)
{
	for(int i = 1; i <= N; i++){
		pay[n][i] = INF;
		visit[i] = 0;
	}

	pay[n][n] = 0;
	int minId; 
	int minVal;
	for(int i = 1; i <= N; i++){
		minId = -1;
		minVal = INF;
		for(int j = 1; j <= N; j++){
			if(visit[j] == 0 && pay[n][j] < minVal){
				minVal = pay[n][j];
				minId = j;
			}
		}

		visit[minId] = 1;
		int tmp;

		for(int j = 0; j < index[minId]; j++){
			tmp = minVal + mtke[minId][dske[minId][j]];
			if(pay[n][dske[minId][j]] > tmp && visit[dske[minId][j]] == 0){
				pay[n][dske[minId][j]] = tmp;
			}
		}
	}
}

void backTrack(int id, int nK, int value)
{
	if(nK == K){
		if(pay[id][1] != INF){
			int tmp = value + pay[id][1];
			if(tmp < ans)
				ans = tmp;
		}
		return;
	}
	if(value > ans)
		return;

	for(int i = 0; i <= K; i++){
		int temp = needVS[i];
		if(mark[temp] == 0 && pay[id][temp] != INF){
			mark[temp] = 1;
			backTrack(temp, nK+1, value + pay[id][temp]);
			mark[temp] = 0;
		}
	}
}

int main()
{
	//freopen("input.txt" , "r", stdin);
	int T; 
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		input();
		bool check = true;
		//cout << tc << endl;
		for(int i = 0; i <= K; i++){
			dijkstra(needVS[i]);
		}
		ans = INF;
		mark[1] = 1;
		backTrack(1,0,0);
		
		if(ans != INF)
			cout  << "Case #" << tc << endl << ans << endl << endl;
		else
			cout  << "Case #" << tc << endl << "-1" << endl << endl;
	}
	return 0;
}