Untitled

#include <iostream>
using namespace std;

const int MAXN = 1000;
const int MAXK = 15;
const long long INF = 1e18;

long long dist[MAXN][MAXN], dp[1 << MAXK][MAXK];
int s[MAXK];

void floydWarshall(int n) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

long long findMinCost(int n, int m, int k) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = (i == j ? 0 : INF);

    for (int i = 0; i < m; i++) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        dist[u-1][v-1] = c;
    }

    floydWarshall(n);

    for (int i = 0; i < (1 << k); i++)
        for (int j = 0; j < k; j++)
            dp[i][j] = INF;

    for (int i = 0; i < k; i++)
        dp[1 << i][i] = dist[0][s[i]];

    for (int mask = 0; mask < (1 << k); mask++) {
        for (int i = 0; i < k; i++) {
            if (mask & (1 << i)) {
                for (int j = 0; j < k; j++) {
                    if (!(mask & (1 << j))) {
                        dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j],
                                                      dp[mask][i] + dist[s[i]][s[j]]);
                    }
                }
            }
        }
    }

    long long result = INF;
    for (int i = 0; i < k; i++)
        result = min(result, dp[(1 << k) - 1][i] + dist[s[i]][0]);

    return (result >= INF ? -1 : result);
}

int main() {
    int T;
	//freopen("input.txt","r",stdin);
    cin >> T;
	for (int tc = 0; tc < T; tc++)
	{

        int n, m, k;
        cin >> n >> m >> k;
        for (int i = 0; i < k; i++) {
            cin >> s[i];
            s[i]--;
        }
        cout << "Case #" << tc+1 << " \n" << findMinCost(n, m, k) << endl;
    }
    return 0;
}