Untitled

// Dijkstra
#include <iostream>
#define MAX 9223372036854775807
#define ll long long
using namespace std;

int n, m, k;
ll key[1001][1001];
ll visited[1001];
ll arr[1001][1001];
ll arrDL[20];
ll arrHV[20];
ll visitedHV[20];
ll Min;

void Dijkstra(int s){
	key[s][s] = 0;
	for(int k=0; k<n; k++){
		ll MinD = MAX;
		int mem = -1;
		for(int i = 1; i<=n; i++){
			if(visited[i] == 0){
				if(MinD > key[s][i]){
					MinD = key[s][i];
					mem = i;
				}
			}
		}
		if(mem == -1)
			return;
		visited[mem] = 1;
		for(int i=1; i<=n; i++){
			if(visited[i] == 0){
				if(key[s][i] > key[s][mem] + arr[mem][i] && arr[mem][i] != 0){
					key[s][i] = key[s][mem] + arr[mem][i];
				}
			}
		}
	}
}

void BackTrack(int dd, ll sum, int cnt){
	
	if(cnt == k){
		if(key[dd][1] == MAX)
			return;
		Min = min(Min, sum + key[dd][1]);
		return;
	}

	if(sum >= Min)
		return;

	for(int i=1; i<k; i++){
		if(visitedHV[i] == 0){
			visitedHV[i] = 1;
			arrHV[cnt] = arrDL[i];
			if(key[dd][arrDL[i]] == MAX)
				return;
			BackTrack(arrDL[i], sum + key[dd][arrDL[i]], cnt + 1);
			visitedHV[i] = 0;
		}
	}

}

void reset(int s){
	for(int i=1; i<=n; i++){
		key[s][i] = MAX;
		visited[i] = 0;
	}
}


void resetBD(){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			arr[i][j] = 0;
		}
	}
	for(int i=0; i<=k+1; i++){
		visitedHV[i] = 0;
		arrDL[i] = 0;
	}
}

int main(){
	//freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	for(int tc=1; tc<=t; tc++){
		cin >> n >> m >> k;
		resetBD();
		int d;
		arrDL[0] = 1;
		for(int i=0; i<k; i++){
			cin >> d;
			arrDL[i+1] = d;
		}
		int x, y, w;
		for(int i=0; i<m; i++){
			cin >> x >> y >> w;
			arr[x][y] = w;
		}

		k = k+1;

		for(int i=0; i<k; i++){
			int s = arrDL[i];
			reset(s);
			Dijkstra(s);
		}

		Min = MAX;
		visitedHV[0] = 1;
		BackTrack(arrDL[0], 0, 1);

		cout << "Case #" << tc << endl;
		if(Min != MAX)
			cout << Min << endl;
		else
			cout << "-1" << endl;
		cout << endl;
	}
	return 0;
}
// BFS
#include <iostream>
#define ll long long
using namespace std;

int n, m, k;
ll MAX = 9223372036854775807;
ll arrDD[1001];
ll key[1001][1001];
ll arr[1001][1001];
ll arrDL[20];
ll visitedBT[1001];
ll visitedBFS[1001];
ll Min;
ll arrKe[1001][1001];
ll len[1001];

typedef struct Point{
	int x, y, w;
};

Point arrTD[1000001];

typedef struct Queue{
	int front, rear;
	Point data[10000001];
};

void init(Queue &Q){
	Q.front = Q.rear = -1;
}

void push(Queue &Q, Point value){
	Q.rear++;
	Q.data[Q.rear] = value;
}

Point top(int flag, Queue &Q){
	Point temp;
	Q.front++;
	temp = Q.data[Q.front];

	for(int i=Q.front; i<=Q.rear; i++){
		int k1 = key[flag][temp.x];
		int k2 = key[flag][Q.data[i].x];

		if(k1 > k2){
			swap(temp.x, Q.data[i].x);
		}

	}

	Q.front--;
	return temp;
}

void pop(Queue &Q){
	Q.front++;
}

bool empty(Queue &Q){
	if(Q.front == Q.rear)
		return true;
	return false;
}

Queue Q;

void BFS(Point P){
	init(Q);
	push(Q, P);
	visitedBFS[P.x] = 1;
	key[P.x][P.x] = 0;
	while(!empty(Q)){
		Point P1;
		P1 = top(P.x, Q);
		pop(Q);

		int u = P1.x;
		for(int i=0; i<len[u]; i++){
			int v = arrKe[u][i];
			if(visitedBFS[v] == 0 && arr[u][v] != 0){
				visitedBFS[v] = 1;
				key[P.x][v] = key[P.x][u] + arr[u][v];

				Point P2;
				P2.x = v;
				push(Q, P2);
			}

		}

	}
}


void BackTrack(int d, ll sum, ll cnt){

	if(cnt == k+1){
		if(key[d][1] != MAX){
			Min = min(Min, sum + key[d][1]);
		}
		return;
	}

	if(sum >= Min)
		return;
	
	for(int i=1; i<k+1; i++){
		int dl = arrDL[i];
		if(visitedBT[dl] == 0 && key[d][dl] != MAX){
			visitedBT[dl] = 1;
			BackTrack(dl, sum + key[d][dl], cnt+1);
			visitedBT[dl] = 0;
		}
	}

}

void resetBFS(int s){
	for(int i=1; i<=n; i++){
		visitedBFS[i] = 0;
	}
	for(int i=1; i<=n; i++){
		key[s][i] = MAX;
	}
}

void resetBT(){
	for(int i=1; i<=n; i++)
		visitedBT[i] = 0;
}

void resetBD(){
	for(int i=1; i<=n; i++){
		arrDD[i] = 0;
		len[i] = 0;
		for(int j=1; j<=n; j++)
			arr[i][j] = 0;
	}
}

int main(){
	//freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	for(int tc=1; tc<=t; tc++){
		cin >> n >> m >> k;
		resetBD();
		int d;

		arrDL[0] = 1;
		for(int i=0; i<k; i++){
			cin >> d;
			arrDL[i+1] = d;
			arrDD[d] = 1;
		}
		int x, y, w;
		for(int i=0; i<m; i++){
			cin >> x >> y >> w;
			arrKe[x][len[x]] = y;
			len[x]++;
			arr[x][y] = w;
		}

		arrDD[1] = 1;
		for(int i=1; i<=n; i++){
			if(arrDD[i] == 1){
				int s = i;
				resetBFS(s);
				Point P;
				P.x = i;
				BFS(P);
			}
		}

		resetBT();
		Min = MAX;
		BackTrack(arrDL[0], 0, 1);

		cout << "Case #" << tc << endl;
		if(Min != MAX)
			cout << Min << endl;
		else
			cout << "-1" << endl;
		cout << endl;
	}
	return 0;
}