#include using namespace std; template void chmin(T &a, T b) { if (b < a) { a = b; } } using graph = vector>>; void dfs(const graph &to, vector &dist, int v, int par) { for (auto [next, l] : to.at(v)) { if (next == par) continue; dist.at(next) = dist.at(v) + l; dfs(to, dist, next, v); } } int main() { constexpr int64_t inf = 1e18; int64_t n, q, c; cin >> n >> q >> c; graph to(n); for (int i = 0; i < n - 1; i++) { int64_t u, v, l; cin >> u >> v >> l; u--; v--; to.at(u).emplace_back(v, l); to.at(v).emplace_back(u, l); } vector x(q); for (int i = 0; i < q; i++) { cin >> x.at(i); x.at(i)--; } vector dist(n, vector(n, int64_t())); for (int i = 0; i < n; i++) { dfs(to, dist.at(i), i, -1); } vector dp(q, vector(n, inf)); dp.at(0).at(x.at(0)) = 0; int64_t mincost_prev = 0; for (int i = 1; i < q; i++) { int64_t mincost = inf; for (int j = 0; j < n; j++) { chmin(dp.at(i).at(j), dp.at(i - 1).at(j) + dist.at(x.at(i - 1)).at(x.at(i))); chmin(dp.at(i).at(j), mincost_prev + dist.at(x.at(i - 1)).at(j) + dist.at(j).at(x.at(i))); for (int k = 0; k < n; k++) { chmin(dp.at(i).at(j), dp.at(i - 1).at(k) + c + dist.at(k).at(j) + dist.at(j).at(x.at(i))); } // chmin(dp.at(i).at(j), dp.at(i - 1).at(j) + c + dist.at(j).at(x.at(i))); chmin(mincost, dp.at(i).at(j)); } mincost_prev = mincost; } cout << dp.at(q - 1).at(x.at(q - 1)) << endl; }