#include using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) begin(v),end(v) template inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } using ll = long long; using pii = pair; constexpr ll INF = 1ll<<30; constexpr ll longINF = 1ll<<60; constexpr ll MOD = 1000000007; constexpr bool debug = false; //---------------------------------// int main() { int N, Q, C; cin >> N >> Q >> C; vector> g(N); REP(i, N - 1) { int u, v, l; scanf("%d %d %d", &u, &v, &l); --u; --v; g[u].emplace_back(v, l); g[v].emplace_back(u, l); } vector X(Q); REP(i, Q) scanf("%d", &X[i]), --X[i]; vector dist(N, vector(N)); REP(i, N) { auto dfs = [&](auto self, int u, ll d, int par) -> void { dist[i][u] = d; for (auto [v, l] : g[u]) { if (v == par) continue; self(self, v, d + l, u); } }; dfs(dfs, i, 0, -1); } vector dp(N), nextdp; // [i] := ビーコンの位置 REP(i, N) dp[i] = dist[X[0]][i]; REP(i, Q - 1) { // X[i] -> X[i + 1] nextdp.assign(N, longINF); REP(j, N) nextdp[j] = dp[j] + dist[X[i]][X[i + 1]]; // ビーコン設置なし queue que; que.emplace(X[i], -1); vector vtx; while (!que.empty()) { auto [u, p] = que.front(); que.pop(); vtx.emplace_back(u); for (auto [v, _] : g[u]) { if (v == p) continue; if (dist[X[i]][v] + dist[v][X[i + 1]] == dist[X[i]][X[i + 1]]) que.emplace(v, u); } } ll mn = *min_element(ALL(dp)); REP(j, vtx.size()) { if (j > 0) mn += dist[vtx[j - 1]][vtx[j]]; chmin(mn, dp[vtx[j]] + C); chmin(nextdp[vtx[j]], mn + dist[vtx[j]][X[i + 1]]); } swap(dp, nextdp); } cout << *min_element(ALL(dp)) << endl; }