#include #include #include using namespace std; int main(){ int N, Q; long long C; while(cin >> N >> Q >> C){ vector>> g(N); for(int i=0;i> u >> v >> l; g[u-1].emplace_back(v-1, l); g[v-1].emplace_back(u-1, l); } vector x(Q); for(auto& t : x){ cin >> t; --t; } long long res = 0; vector seq(1, x[0]); vector cost(1, -C); for(int i=0;i+1 dist(N, -1); vector prev(N, -1); dist[x[i+1]] = 0; queue qu; qu.push(x[i+1]); while(!qu.empty()){ int p = qu.front(); qu.pop(); for(auto& nd : g[p]){ if(dist[nd.first] != -1) continue; dist[nd.first] = dist[p] + nd.second; prev[nd.first] = p; qu.push(nd.first); } } long long whole = dist[x[i]]; res += whole; int cur = x[i]; while(true){ int next = prev[cur]; if(next == -1) break; seq.push_back(next); cost.push_back(whole-dist[next]-C); cur = next; } } vector> posList(N); for(int i=0;i next(seq.size(), -1); for(auto& v : posList){ for(int i=0;i+1 dp(seq.size(), 0); for(int i=0;i+1