Tuantrangmatquocsol

#include <iostream>

using namespace std;

int n, m, k;
int diadiem[1005];
int oo = 99999999;
struct tuyenduong {
	int u, v, c;
};

tuyenduong road[1005];
int final[1005][1005];
int visit[1005];
int dist[1005][1005];
int tmp_dist[1005];
int cur;
int dinhxet[1005];
int check[1005];
int ans;
void swap(int i, int j) {
	int tmp = dinhxet[i];
	dinhxet[i] = dinhxet[j];
	dinhxet[j] = tmp;
}


void disktra(int dinh) {
	for (int i = 1; i <= n; i++) {
		tmp_dist[i] = oo;
		visit[i] = 0;
	}
	cur = 1;
	dinhxet[cur] = dinh;
	tmp_dist[dinh] = 0;
	while (true) {
		int min_dinh = -1;
		int min_dist = oo;
		int tmp_pos;
		for (int k = 1; k <= cur; k++) {
			int i = dinhxet[k];
			if (visit[i] == 0 && tmp_dist[i] < min_dist) {
				min_dinh = i;
				tmp_pos = k;
				min_dist = tmp_dist[i];
			}
		}

		if (min_dinh == -1) {
			break;
		}
		//cout << min_dinh << endl;
		visit[min_dinh] = 1;
		swap(tmp_pos, cur);
		cur--;
		for (int i = 1; i <= n; i++) {
			if (dist[min_dinh][i] != oo) {
				if (tmp_dist[i] > tmp_dist[min_dinh] + dist[min_dinh][i]) {
					tmp_dist[i] = tmp_dist[min_dinh] + dist[min_dinh][i];
					final[dinh][i] = tmp_dist[i];
					cur++;
					dinhxet[cur] = i;
				}
			}
		}

	}
}

bool checkk() {
	for (int i = 1; i <= k; i++) {
		if (check[diadiem[i]] == 0) {
			return false;
		}
	}
	return true;
}
void backtrack(long long current, long long index, long long cost)
{
	if (index == k)
	{
		cost += final[current][1];
		if (cost < ans) ans = cost;
		return;
	}
	
	if (cost > ans) return;
	for (long long i = 1; i <= k; i++)
	if (check[i] == 0 && final[current][diadiem[i]] != oo)
	{
		check[i] = 1;
		backtrack(diadiem[i], index + 1, cost + final[current][diadiem[i]]);
		check[i] = 0;
	}
}


void solve(int testcase) {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dist[i][j] = oo;
			final[i][j] = oo;
		}		
	}
	for (int i = 1; i <= k; i++) {
		cin >> diadiem[i];
	}
	
	for (int i = 1; i <= m; i++) {
		cin >> road[i].u >> road[i].v >> road[i].c;
		dist[road[i].u][road[i].v] = road[i].c;
	}

	disktra(1);
	
	
	for (int i = 1; i <= k; i++) {
		disktra(diadiem[i]);
	}
	
	
	
	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << final[i][j] << " ";
		}
		cout << endl;
	}
	*/
	
	
	
	for (int i = 1; i <= k; i++) {
		check[i] = 0;
	}
	
	ans = oo;
	backtrack(1, 0, 0);
	if (ans == oo) {
		ans = -1;
	}
	cout << "Case #" << testcase << endl;
	cout << ans << endl;
	cout << endl;

}

int main() {
	//freopen("Text.txt", "r", stdin);
	int t; cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
	return 0;
}