#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; using ll = long long; template using vec = vector; template using vvec = vector>; template bool chmin(T& a,T b){if(a>b) {a = b; return true;} return false;} template bool chmax(T& a,T b){if(a=0;i--) #define all(x) (x).begin(),(x).end() #define debug(x) cerr << #x << " = " << (x) << endl; struct edge{ int to,d; }; template struct DualSegmentTree { int sz, height; vector 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(sz0;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>=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]; } }; class HeavLightDecomposition{ public: vvec g; vec sz,in,out,head,par; int pos; void dfs_sz(int cur,int p){ sz[cur] = 1; par[cur] = p; for(auto& e:g[cur]) if(e.to!=p){ dfs_sz(e.to,cur); sz[cur] += sz[e.to]; if(sz[e.to]>sz[g[cur][0].to]) swap(e,g[cur][0]); } } void dfs_hld(int cur,int p){ in[cur] = pos++; for(auto& e:g[cur]) if(e.to!=p){ head[e.to] = (e.to==g[cur][0].to? head[cur]:e.to); dfs_hld(e.to,cur); } out[cur] = pos; } public: HeavLightDecomposition(){} HeavLightDecomposition(int N,int root,vvec tree): g(tree),sz(N),in(N),out(N),head(N),par(N){ pos = 0; dfs_sz(root,-1); dfs_hld(root,-1); } int lca(int u,int v){ while(true){ if(in[u]>in[v]) swap(u,v); if(head[u]==head[v]) return u; v = par[head[v]]; } } template void update(int u,int v,const T& x,const G& g, bool isedge=false){ while(true){ if(in[u]>in[v]) swap(u,v); if(head[u]==head[v]) break; g(in[head[v]],in[v]+1,x); v = par[head[v]]; } g(in[u]+isedge,in[v]+1,x); } template T query(int u,int v,const T &e,const F& f,const Q& q,bool isedge=false){ T l = e,r = e; while(true){ if(in[u]>in[v]){ swap(u,v); swap(l,r); } if(head[u]==head[v]) break; l = f(q(in[head[v]],in[v]+1),l); v = par[head[v]]; } //非可換演算のときは左を反転! //f(rev(f(q(a,b),l),r); return f(f(q(in[u]+isedge,in[v]+1),l),r); } }; constexpr ll inf = 1e18; auto op = [](ll a,ll b){return min(a,b);}; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,Q,C; cin >> N >> Q >> C; vvec g(N); rep(i,N-1){ int a,b,c; cin >> a >> b >> c; a--,b--; g[a].push_back({b,c}); g[b].push_back({a,c}); } vec X(Q); rep(i,Q){ cin >> X[i]; X[i]--; } HeavLightDecomposition HLD(N,0,g); vec D(N); auto dfs = [&](auto&& self,int cur,int par)->void{ for(auto& [to,d]:g[cur]) if(to!=par){ D[to] = D[cur]+d; self(self,to,cur); } }; dfs(dfs,0,-1); auto dist = [&](int a,int b){ return D[a]+D[b]-2*D[HLD.lca(a,b)]; }; DualSegmentTree seg(N,op,inf); vec dp; rep(i,Q) dp.push_back(seg); dp[0].update(HLD.in[X[0]],HLD.in[X[0]]+1,0); rep(i,Q-1){ auto update = [&](int l,int r,ll x){ dp[i+1].update(l,r,x); }; ll best = inf; rep(j,N){ int n = HLD.in[j]; if(dp[i][n]==inf) continue; ll val = dp[i][n]+dist(X[i],X[i+1]); HLD.update(j,j,val,update); chmin(best,val); ll c = dp[i][n]+dist(j,X[i+1])+C; HLD.update(j,X[i+1],c,update); } HLD.update(X[i],X[i+1],best,update); } ll ans = inf; rep(i,N) chmin(ans,dp[Q-1][i]); cout << ans << "\n"; }