#include struct Graph { struct Edge { int src, dst; int64_t cost; int other(int v) const { assert(v == src or v == dst); return src ^ dst ^ v; } }; std::vector edges; std::vector>> adj; Graph() {} explicit Graph(int n) : adj(n) {} int n() const { return std::size(adj); } int m() const { return std::size(edges); } int add_edge(const Edge& e, bool directed) { assert(0 <= e.src), assert(e.src < n()); assert(0 <= e.dst), assert(e.dst < n()); int id = m(); edges.push_back(e); adj[e.src].emplace_back(e.dst, id); if (not directed) adj[e.dst].emplace_back(e.src, id); return id; } }; struct DfsTree : Graph { using T = decltype(Edge::cost); std::vector root; std::vector pv; std::vector pe; std::vector order; std::vector in; std::vector out; std::vector sz; std::vector depth; std::vector min_depth; std::vector dist; std::vector last; int num_trials; DfsTree() {} explicit DfsTree(int n) : Graph(n), root(n, -1), pv(n, -1), pe(n, -1), in(n, -1), out(n, -1), sz(n, -1), depth(n, -1), min_depth(n, -1), dist(n, std::numeric_limits::max()), last(n, -1), num_trials(0) {} int add_edge(const Edge& e) { return Graph::add_edge(e, false); } void dfs(int r, bool clear_order = true) { assert(0 <= r), assert(r < n()); root[r] = r; pv[r] = -1; pe[r] = -1; if (clear_order) order.clear(); depth[r] = 0; dist[r] = T{}; dfs_impl(r); ++num_trials; } void dfs_all() { std::fill(std::begin(root), std::end(root), -1); for (int v = 0; v < n(); ++v) if (root[v] == -1) dfs(v, v == 0); } int deeper(int id) const { assert(0 <= id), assert(id < m()); int a = edges[id].src; int b = edges[id].dst; return depth[a] < depth[b] ? b : a; } bool is_tree_edge(int id) const { assert(0 <= id), assert(id < m()); return id == pe[deeper(id)]; } bool is_ancestor(int u, int v) const { assert(0 <= u), assert(u < n()); assert(0 <= v), assert(v < n()); return in[u] <= in[v] and out[v] <= out[u]; } private: void dfs_impl(int v) { in[v] = std::size(order); order.push_back(v); sz[v] = 1; min_depth[v] = depth[v]; last[v] = num_trials; for (auto [u, id] : adj[v]) { if (id == pe[v]) continue; if (last[u] == num_trials) { min_depth[v] = std::min(min_depth[v], depth[u]); continue; } root[u] = root[v]; pv[u] = v; pe[u] = id; depth[u] = depth[v] + 1; dist[u] = dist[v] + edges[id].cost; dfs_impl(u); sz[v] += sz[u]; min_depth[v] = std::min(min_depth[v], min_depth[u]); } out[v] = std::size(order); } }; struct HldTree : DfsTree { std::vector head; HldTree() {} explicit HldTree(int n) : DfsTree(n), head(n, -1) {} void build(int r, bool clear_order = true) { assert(0 <= r), assert(r < n()); dfs(r, clear_order); order.erase(std::end(order) - sz[r], std::end(order)); head[r] = r; build_impl(r); } void build_all() { std::fill(std::begin(root), std::end(root), -1); for (int v = 0; v < n(); ++v) if (root[v] == -1) build(v, v == 0); } int lca(int u, int v) const { assert(0 <= u), assert(u < n()); assert(0 <= v), assert(v < n()); assert(root[u] == root[v]); while (true) { if (in[u] > in[v]) std::swap(u, v); if (head[u] == head[v]) return u; v = pv[head[v]]; } } int d(int u, int v) const { assert(0 <= u), assert(u < n()); assert(0 <= v), assert(v < n()); assert(root[u] == root[v]); return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } T distance(int u, int v) const { assert(0 <= u), assert(u < n()); assert(0 <= v), assert(v < n()); assert(root[u] == root[v]); return dist[u] + dist[v] - 2 * dist[lca(u, v)]; } int la(int v, int d) const { assert(0 <= v), assert(v < n()); assert(0 <= d), assert(d <= depth[v]); while (depth[head[v]] > d) v = pv[head[v]]; return order[in[head[v]] + (d - depth[head[v]])]; } int next(int src, int dst) const { assert(0 <= src), assert(src < n()); assert(0 <= dst), assert(dst < n()); assert(root[src] == root[dst]); assert(src != dst); if (not is_ancestor(src, dst)) return pv[src]; return la(dst, depth[src] + 1); } int next(int src, int dst, int k) const { assert(0 <= src), assert(src < n()); assert(0 <= dst), assert(dst < n()); assert(root[src] == root[dst]); assert(k >= 0); int v = lca(src, dst); if (k <= depth[src] - depth[v]) return la(src, depth[src] - k); k -= depth[src] - depth[v]; assert(k <= depth[dst] - depth[v]); return la(dst, depth[v] + k); } template void apply(int src, int dst, bool vertex, Function f) const { assert(0 <= src), assert(src < n()); assert(0 <= dst), assert(dst < n()); assert(root[src] == root[dst]); int v = lca(src, dst); while (head[src] != head[v]) { f(in[src] + 1, in[head[src]]); src = pv[head[src]]; } if (vertex) f(in[src] + 1, in[v]); else if (src != v) f(in[src] + 1, in[v] + 1); auto rec = [&](auto self, int to) -> void { if (head[v] == head[to]) { if (v != to) f(in[v] + 1, in[to] + 1); return; } self(self, pv[head[to]]); f(in[head[to]], in[to] + 1); }; rec(rec, dst); } template int search(int src, int dst, bool vertex, Searcher f) const { assert(0 <= src), assert(src < n()); assert(0 <= dst), assert(dst < n()); assert(root[src] == root[dst]); int res = -1; apply(src, dst, vertex, [&](int l, int r) { if (res != -1) return; int i = f(l, r); if (l > r) std::swap(l, r); if (l <= i and i < r) res = vertex ? order[i] : pe[order[i]]; }); return res; } private: void build_impl(int v) { in[v] = std::size(order); order.push_back(v); auto pos = std::partition(std::begin(adj[v]), std::end(adj[v]), [&](auto e) { return e.second == pe[e.first]; }); auto it = std::max_element(std::begin(adj[v]), pos, [&](auto a, auto b) { return sz[a.first] < sz[b.first]; }); if (it != std::begin(adj[v])) std::iter_swap(std::begin(adj[v]), it); std::partition(pos, std::end(adj[v]), [&](auto e) { return e.second == pe[v]; }); for (auto [u, id] : adj[v]) { if (id != pe[u]) break; head[u] = u == adj[v].front().first ? head[v] : u; build_impl(u); } out[v] = std::size(order); } }; #pragma region my_template struct Rep { struct I { int i; void operator++() { ++i; } int operator*() const { return i; } bool operator!=(I o) const { return i < *o; } }; const int l_, r_; Rep(int l, int r) : l_(l), r_(r) {} Rep(int n) : Rep(0, n) {} I begin() const { return {l_}; } I end() const { return {r_}; } }; struct Per { struct I { int i; void operator++() { --i; } int operator*() const { return i; } bool operator!=(I o) const { return i > *o; } }; const int l_, r_; Per(int l, int r) : l_(l), r_(r) {} Per(int n) : Per(0, n) {} I begin() const { return {r_ - 1}; } I end() const { return {l_ - 1}; } }; template struct Fix : private F { Fix(F f) : F(f) {} template decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, std::forward(args)...); } }; template T scan() { T res; std::cin >> res; return res; } template bool chmin(T& a, U&& b) { return b < a ? a = std::forward(b), true : false; } template bool chmax(T& a, U&& b) { return a < b ? a = std::forward(b), true : false; } #ifndef LOCAL #define DUMP(...) void(0) template constexpr int OjLocal = OnlineJudge; #endif using namespace std; #define ALL(c) begin(c), end(c) #pragma endregion constexpr auto Inf = numeric_limits::max() / 2; int main() { cin.tie(nullptr)->sync_with_stdio(false); cout << fixed << setprecision(20); int n = scan(); int q = scan(); int c = scan(); HldTree g(n); for (int _ = n - 1; _--;) g.add_edge({scan() - 1, scan() - 1, scan()}); vector x(q); generate(ALL(x), [] { return scan() - 1; }); vector> d(n); for (int s : Rep(n)) { g.dfs(s); d[s] = g.dist; } vector f(n, +Inf); f[x[0]] = 0; g.build_all(); for (int i : Rep(q - 1)) { vector nf(n, +Inf); for (int v : Rep(n)) chmin(nf[v], f[v] + d[x[i]][x[i + 1]]); auto mn = *min_element(ALL(f)) + d[x[i]][x[i + 1]]; for (int u = x[i];; u = g.next(u, x[i + 1])) { chmin(nf[u], mn); if (u == x[i + 1]) break; } mn = +Inf; for (int v = x[i];; v = g.next(v, x[i + 1])) { chmin(mn, f[v] + c + d[v][x[i + 1]]); chmin(nf[v], mn); // for (int u = v;; u = g.next(u, x[i + 1])) { // chmin(nf[u], f[v] + c + d[v][x[i + 1]]); // if (u == x[i + 1]) break; // } if (v == x[i + 1]) break; } f = move(nf); } cout << *min_element(ALL(f)) << '\n'; }