Untitled

#include<iostream>
using namespace std;
int TC, N, M, K, a[1005][1005], c[1005][1005], b[20], vi[1005], di[1005], pa[1005], vib[20], hv[20], minre, dp[1005][1005];
int int_max = 2147483647;

int mind() {
    int mink = int_max, mini = -1;
    for(int i = 0; i < N; i++) {
        if(vi[i] == 0 && di[i] < mink) {
            mink = di[i], mini = i;
        }
    }
    return mini;
}

int findMind(int x,  int y) {
    fill_n(di, N, int_max);
    fill_n(vi, N, 0);
    fill_n(pa, N, -1);
    di[x] = 0;
    for(int i = 0; i < N - 1; i++) {
        int id = mind();
        if(id == -1) break;
        vi[id] = 1;
        for(int j = 1; j <= a[id][0]; j++) {
            if(vi[ a[id][j] ] == 0 && di[id] != int_max && di[id] + c[id][j] < di[ a[id][j] ]) {
                di[ a[id][j] ] = di[id] + c[id][j];
                pa[ a[id][j] ] = id;
            }
        }
    }
    int kc = di[y] == int_max ? -1 : di[y];
    for(int i = 0; i < N; i++) {
        if(di[i] != int_max) {
            dp[x][i] = di[i];
        }
    }
    //int tmp = y;
    //while(pa[y] != -1) {
    //    for(int i = 0; i < )
    //    pa[y];
    //}
    return kc;
}

void doing(int k, int c, int pre) {
    if(c >= minre) return;
    if(k == K) {
        /*for(int i = 0; i < K; i++) {
            cout << b[hv[i]] << " ";
        }
        cout << endl;*/
        int tmpc;
        if(dp[b[pre]][0] == -1) {
            tmpc = findMind(b[pre], 0);
        } else {
            tmpc = dp[b[pre]][0];
        }
        if(c + tmpc < minre) minre = c + tmpc;
        return;
    }
    for(int i = 0; i < K; i++) {
        if(vib[i] == 0) {
            //hv[k] = i;
            int ch = 1;
            int tmpd;
            if(k == 0) {
                if(dp[0][b[i]] == -1) {
                    tmpd = findMind(0, b[i]);
                    if(tmpd == -1) {
                        ch = 0;
                    }
                } else {
                    tmpd = dp[0][b[i]];
                }
            } else {
                if(dp[b[pre]][b[i]] == -1) {
                    tmpd = findMind(b[pre], b[i]);
                    if(tmpd == -1) {
                        ch = 0;
                    }
                } else {
                    tmpd = dp[b[pre]][b[i]];
                }
            }
            if(ch == 1) {
                vib[i] = 1;
                doing(k + 1, c + tmpd, i);
                vib[i] = 0;   
            }
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> TC;
    for(int tc = 1; tc <= TC; tc++) {
        cin >> N >> M >> K;
        for(int i = 0; i < K; i++) cin >> b[i];
        for(int i = 0; i < K; i++) b[i]--;
        fill_n(vib, K, 0);
        for(int i = 0; i < N; i++) fill_n(dp[i], N, -1);
        for(int i = 0; i < M; i++) {
            int x, y, ci;
            cin >> x >> y >> ci;
            x--, y--;
            a[x][0]++;
            a[x][a[x][0]] = y, c[x][a[x][0]] = ci;
        }
        minre = int_max;
        /*cout << "HJ " << findMind(0, 1) << endl;
        cout << "HJ " << findMind(1, 4) << endl;
        cout << "HJ " << findMind(4, 0) << endl;
        
        cout << "HJ " << findMind(0, 4) << endl;
        for(int i = 0; i < N; i++) {
            cout << pa[i] << " " ;
        }
        cout << endl;
        cout << "HJ " << findMind(4, 1) << endl;
        cout << "HJ " << findMind(1, 0) << endl;*/
        doing(0, 0, -1);
        minre = minre == int_max ? -1 : minre;
        cout << "Case #" << tc << endl << minre << endl << endl;
    }
    return 0;
}