#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; using ull = unsigned long long; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } //template T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); }return a; } //mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); constexpr long long INF = 1LL << 60; constexpr int inf = 1000000007; constexpr long long mod = 1000000007LL; //constexpr long long mod = 998244353; struct HLD { vector sz, in, out, head, par; vector> g; HLD() {} HLD(vector>& _g) : g(_g), sz(_g.size()), in(_g.size()), out(_g.size()), head(_g.size()), par(_g.size()) { build(); } void dfs_sz(int cur, int pre) { sz[cur] = 1; for (int& next : g[cur]) { if (next == pre) continue; dfs_sz(next, cur); par[next] = cur; sz[cur] += sz[next]; if (sz[next] > sz[g[cur][0]]) swap(next, g[cur][0]); } } void dfs_hld(int cur, int pre, int& idx) { in[cur] = idx++; for (int& next : g[cur]) { if (next == pre) continue; if (next == g[cur][0]) head[next] = head[cur]; else head[next] = next; dfs_hld(next, cur, idx); } out[cur] = idx; } void build() { dfs_sz(0, -1); int idx = 0; dfs_hld(0, -1, idx); } void build(vector>& _g) { g = _g; sz.resize(g.size()); in.resize(g.size()); out.resize(g.size()); head.resize(g.size()); par.resize(g.size()); dfs_sz(0, -1); int idx = 0; dfs_hld(0, -1, idx); } int lca(int u, int v) { for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) return u; } } //[l, r)の区間集合を返す vector> path_query(int u, int v, bool edge = false) { vector> ret; for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) break; ret.emplace_back(in[head[v]], in[v] + 1); } ret.emplace_back(in[u] + edge, in[v] + 1); return ret; } }; template< typename OperatorMonoid, typename H > struct DualSegmentTree { int sz, height; vector< OperatorMonoid > lazy; const H h; const OperatorMonoid OM0; DualSegmentTree(int n, const H h, const OperatorMonoid& OM0) : h(h), OM0(OM0) { sz = 1; height = 0; while (sz < n) sz <<= 1, height++; lazy.assign(2 * sz, OM0); } inline void propagate(int k) { if (lazy[k] != OM0) { lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]); lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]); lazy[k] = OM0; } } inline void thrust(int k) { for (int i = height; i > 0; i--) propagate(k >> i); } void update(int a, int b, const OperatorMonoid& x) { thrust(a += sz); thrust(b += sz - 1); for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) lazy[l] = h(lazy[l], x), ++l; if (r & 1) --r, lazy[r] = h(lazy[r], x); } } OperatorMonoid operator[](int k) { thrust(k += sz); return lazy[k]; } }; template< typename OperatorMonoid, typename H > DualSegmentTree< OperatorMonoid, H > get_dual_segment_tree(int N, const H& h, const OperatorMonoid& OM0) { return { N, h, OM0 }; } struct Edge { int from, to; ll cost; Edge(int from, int to, ll cost) :from(from), to(to), cost(cost) {} }; vector bfs(int st, vector>>& g) { int n = g.size(); vector d(n, INF); d[st] = 0; queue q; q.emplace(st); while (!q.empty()) { int cur = q.front(); q.pop(); for (auto [nxt, len] : g[cur]) { if (chmin(d[nxt], d[cur] + len)) { q.emplace(nxt); } } } return d; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, kkt; cin >> n >> kkt; ll C; cin >> C; vector edges; edges.reserve(n - 1); vector> g(n); vector>> tg(n); for (int i = 0; i < n - 1; i++) { int u, v, l; cin >> u >> v >> l; u--; v--; edges.emplace_back(u, v, l); g[u].emplace_back(v); g[v].emplace_back(u); tg[u].emplace_back(v, l); tg[v].emplace_back(u, l); } vector> dist(n); for (int i = 0; i < n; i++) dist[i] = bfs(i, tg); HLD hld(g); auto f1 = [](ll a, ll b) {return min(a, b); }; auto f2 = [](ll a, ll b) { return min(a, b); }; auto lsg = get_dual_segment_tree(n, f2, INF); vector d(kkt, lsg); vector x(kkt); for (int i = 0; i < kkt; i++) cin >> x[i], x[i]--; d[0].update(hld.in[x[0]], hld.in[x[0]] + 1, 0); for (int jupi = 1; jupi < kkt; jupi++) { int cur = x[jupi]; int pre = x[jupi - 1]; ll p = INF; for (int j = 0; j < n; j++) { chmin(p, d[jupi - 1][j]); } for (auto [l, r] : hld.path_query(pre, cur)) { d[jupi].update(l, r, p + dist[pre][cur]); } for (int j = 0; j < n; j++) { ll t = dist[pre][cur]; ll p = d[jupi - 1][hld.in[j]]; if (p == INF) continue; d[jupi].update(hld.in[j], hld.in[j] + 1, p + t); if (C + dist[j][cur] < t) { for (auto [l, r] : hld.path_query(j, cur)) { d[jupi].update(l, r, p + C + dist[j][cur]); } } } } ll res = INF; for (int i = 0; i < n; i++) chmin(res, d.back()[i]); cout << res << "\n"; }