#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 Monoid, typename OperatorMonoid, typename F, typename G, typename H > struct LazySegmentTree { int sz, height; vector< Monoid > data; vector< OperatorMonoid > lazy; const F f; const G g; const H h; const Monoid M1; const OperatorMonoid OM0; LazySegmentTree(int n, const F f, const G g, const H h, const Monoid& M1, const OperatorMonoid OM0) : f(f), g(g), h(h), M1(M1), OM0(OM0) { sz = 1; height = 0; while (sz < n) sz <<= 1, height++; data.assign(2 * sz, M1); lazy.assign(2 * sz, OM0); } void set(int k, const Monoid& x) { data[k + sz] = x; } void build() { for (int k = sz - 1; k > 0; k--) { data[k] = f(data[2 * k + 0], data[2 * k + 1]); } } 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]); data[k] = apply(k); lazy[k] = OM0; } } inline Monoid apply(int k) { return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]); } inline void recalc(int k) { while (k >>= 1) data[k] = f(apply(2 * k + 0), apply(2 * k + 1)); } inline void thrust(int k) { for (int i = height; i > 0; i--) propagate(k >> i); } void update(int a, int b, const OperatorMonoid& x) { if (a >= b) return; 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); } recalc(a); recalc(b); } Monoid query(int a, int b) { if (a >= b) return M1; thrust(a += sz); thrust(b += sz - 1); Monoid L = M1, R = M1; for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) L = f(L, apply(l++)); if (r & 1) R = f(apply(--r), R); } return f(L, R); } Monoid operator[](const int& k) { return query(k, k + 1); } template< typename C > int find_subtree(int a, const C& check, Monoid& M, bool type) { while (a < sz) { propagate(a); Monoid nxt = type ? f(apply(2 * a + type), M) : f(M, apply(2 * a + type)); if (check(nxt)) a = 2 * a + type; else M = nxt, a = 2 * a + 1 - type; } return a - sz; } template< typename C > int find_first(int a, const C& check) { Monoid L = M1; if (a <= 0) { if (check(f(L, apply(1)))) return find_subtree(1, check, L, false); return -1; } thrust(a + sz); int b = sz; for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if (a & 1) { Monoid nxt = f(L, apply(a)); if (check(nxt)) return find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } template< typename C > int find_last(int b, const C& check) { Monoid R = M1; if (b >= sz) { if (check(f(apply(1), R))) return find_subtree(1, check, R, true); return -1; } thrust(b + sz - 1); int a = sz; for (b += sz; a < b; a >>= 1, b >>= 1) { if (b & 1) { Monoid nxt = f(apply(--b), R); if (check(nxt)) return find_subtree(b, check, R, true); R = nxt; } } return -1; } }; template< typename Monoid, typename OperatorMonoid, typename F, typename G, typename H > LazySegmentTree< Monoid, OperatorMonoid, F, G, H > get_lazy_segment_tree (int N, const F& f, const G& g, const H& h, const Monoid& M1, const OperatorMonoid& OM0) { return { N, f, g, h, M1, 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_lazy_segment_tree(n, f1, f2, f2, INF, 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]; for (int j = 0; j < n; j++) { ll t = dist[pre][cur]; ll p = d[jupi - 1].query(hld.in[j], hld.in[j] + 1); d[jupi].update(hld.in[j], hld.in[j] + 1, p + t); for (auto [l, r] : hld.path_query(pre, cur)) { d[jupi].update(l, r, p + t); } for (auto [l, r] : hld.path_query(j, cur)) { d[jupi].update(l, r, p + C + dist[j][cur]); } } } cout << d.back().query(0, n) << "\n"; }