DAY 6 TEST

3
5 10 3
1 3 437
1 2 282
1 5 328
1 2 519
1 2 990
2 3 837
2 4 267
2 3 502
3 5 613
4 5 132
1 3 4
10 13 4
1 6 484
1 3 342
2 3 695
2 3 791
2 8 974
3 9 526
4 9 584
4 7 550
5 9 914
6 7 444
6 8 779
6 10 350
8 8 394
9 10 3 7
10 9 4
1 2 330
1 3 374
1 6 194
2 4 395
2 5 970
2 10 117
3 8 209
4 9 253
5 7 864
8 5 10 6

437
526
641

#include <queue>
#include <cstdio>
#include <cstring>

template <class cls>
inline cls min(const cls & a, const cls & b) {
    return a < b ? a : b;
}

const int mxn = 100005;
const int mxm = 500005;
const int inf = 0x3f3f3f3f;

int n, m, k;

int points[mxn];

int tot;
int hd[mxn];
int nt[mxm];
int to[mxm];
int vl[mxm];

inline void add_edge(int u, int v, int w) {
    nt[++tot] = hd[u];
    to[tot] = v;
    vl[tot] = w;
    hd[u] = tot;
}

int dis[mxn];

struct data {
    int u, d;

    data(int _u, int _d) :
        u(_u), d(_d) {}
    
    bool operator < (const data & that) const {
        return d > that.d;
    }
};

std::priority_queue<data> heap;

int main() {
    int cas;
    scanf("%d", &cas);
    for (int c = 0; c < cas; ++c) {
        scanf("%d%d%d", &n, &m, &k);
        memset(hd, 0, sizeof(int) * (n + 5)); tot = 0;
        for (int i = 0, u, v, w; i < m; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            add_edge(u, v, w);
            add_edge(v, u, w);
        }
        for (int i = 0; i < k; ++i)
            scanf("%d", points + i);
        int ans = inf;
        for (int i = 1; i < k; i <<= 1) {
            memset(dis, inf, sizeof(int) * (n + 5));
            for (int j = 0, p; j < k; ++j)
                if (p = points[j], (j & i) == 0)
                    heap.push(data(p, dis[p] = 0));
            while (!heap.empty()) {
                int u = heap.top().u;
                int d = heap.top().d;
                heap.pop();
                if (dis[u] != d)
                    continue;
                for (int e = hd[u], v, w; e; e = nt[e])
                    if (v = to[e], w = vl[e], dis[v] > d + w)
                        heap.push(data(v, dis[v] = d + w));
            }
            for (int j = 0, p; j < k; ++j)
                if (p = points[j], (j & i) != 0)
                    ans = min(ans, dis[p]);
        }
        printf("%d\n", ans == inf ? -1 : ans);
    }
    return 0;
}

3
5 10 5
4 10 8 1 10
1 3
1 4
1 5
1 3
2 1
2 5
4 3
4 3
4 5
5 1
1 4
4 6
1 9
4 7
2 9
5 10 5
2 8 8 10 10
2 1
2 3
3 2
3 4
3 1
3 2
3 4
4 1
5 4
5 1
1 4
2 3
4 7
3 10
1 5
5 10 5
9 9 8 2 1
1 5
1 5
2 1
2 4
2 4
2 4
3 2
3 1
4 3
4 3
5 9
3 9
2 7
5 1
5 4

40
60
90
70
90
8
30
70
100
10
9
81
63
1
4

3
5 5
3 2 1 1 1
1 2
2 3
2 5
3 4
2 3 4 1
1 2 1
2 3 5 1
2 1 5 3
2 4 4 3
5 5
1 2 1 2 2
1 2
2 3
2 4
3 5
1 1 2
1 3 2
1 2 2
2 4 2 2
2 1 4 1
5 5
2 1 1 1 1
1 2
1 4
2 3
4 5
2 4 2 1
1 1 1
2 1 4 1
2 3 3 1
2 2 2 2

2
3
1
0
2
0
2
2
1
0