1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1100
#define MAXM 1000000
#define INF 0x3fffffff              //防止后面溢出，这个不能太大
struct Graph {
    struct Edge {
        long long to, next;
        long long cost;
    } edge[MAXM];
    long long head[MAXN];
    long long tot;
    void init(long long n) {
        tot = 0;
        memset(head, -1, sizeof(long long) * (n + 1));
    }
    void add_edge(long long from, long long to, long long value) {
        edge[tot].to = to;
        edge[tot].cost = value;
        edge[tot].next = head[from];
        head[from] = tot++;
    }
};
struct Dijkstra {
    long long low_cost[MAXN];
    bool vis[MAXN];
    long long pre[MAXN];
    void solve(long long b, long long e, long long start, Graph &graph) {
        for (long long i = b; i < e; i++) {
            low_cost[i] = INF;
            vis[i] = false;
            pre[i] = -1;
        }
        low_cost[start] = 0;
        vis[start] = true;
        long long cur_edge = graph.head[start];
        while (cur_edge != -1) {
            if (!vis[graph.edge[cur_edge].to] &&
                low_cost[start] + graph.edge[cur_edge].cost < low_cost[graph.edge[cur_edge].to]) {
                low_cost[graph.edge[cur_edge].to] = low_cost[start] + graph.edge[cur_edge].cost;
                pre[graph.edge[cur_edge].to] = start;
            }
            cur_edge = graph.edge[cur_edge].next;
        }
        for (long long j = b; j < e - 1; j++) {
            long long k = -1;
            long long Min = INF;
            for (long long i = b; i < e; i++) {
                if (!vis[i] && low_cost[i] < Min) {
                    Min = low_cost[i];
                    k = i;
                }
            }
            if (k == -1)
                break;
            vis[k] = true;
            cur_edge = graph.head[k];
            while (cur_edge != -1) {
                if (!vis[graph.edge[cur_edge].to] &&
                    low_cost[k] + graph.edge[cur_edge].cost < low_cost[graph.edge[cur_edge].to]) {
                    low_cost[graph.edge[cur_edge].to] = low_cost[k] + graph.edge[cur_edge].cost;
                    pre[graph.edge[cur_edge].to] = k;
                }
                cur_edge = graph.edge[cur_edge].next;
            }
        }
    }
};
Graph graph;
Dijkstra dijkstra1, dijkstra2;
int k_node[MAXN];
void solve() {
    long long t;
    cin >> t;
    long long v, e, s, k, c;
    for (int ts = 0; ts < t; ++ts) {
        cin >> v >> e >> s >> k >> c;
        graph.init(v + 1);
        for (int i = 0; i < k; ++i) {
            cin >> k_node[i];
        }
        long long from, to, value;
        for (long long i = 0; i < e; ++i) {
            cin >> from >> to >> value;
            graph.add_edge(from, to, value);
            graph.add_edge(to, from, value);
        }
        dijkstra1.solve(1, v + 1, s, graph);//第一次跑dijkstra
        for (int i = 0; i < k; ++i) {
            graph.add_edge(0, k_node[i], 0); // 这里设定超级源点为0，建立从0到每一个团队起点的边，权值为0
        }
        dijkstra2.solve(0, v + 1, 0, graph);//第二次跑dijkstra
        long long s_min_max = 0;
        for (long long i = 1; i < v + 1; ++i)
            s_min_max = max(s_min_max, dijkstra1.low_cost[i]);
        long long k_min_max = 0;
        for (long long i = 1; i < v + 1; ++i)
            k_min_max = max(k_min_max, dijkstra2.low_cost[i]);
        if (s_min_max <= c * k_min_max)//考虑到精度问题，这里用乘法代替
            cout << s_min_max << endl;
        else
            cout << k_min_max << endl;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long long test_index_for_debug = 1;
    char acm_local_for_debug;
    while (cin >> acm_local_for_debug) {
        cin.putback(acm_local_for_debug);
        if (test_index_for_debug > 100) {
            throw runtime_error("Check the stdin!!!");
        }
        auto start_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << ":" << endl;
        solve();
        auto end_clock_for_debug = clock();
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "\n--------------------------------------------------" << endl;
    }
#else
    solve();
#endif
    return 0;
}