#line 2 "cpplib/util/template.hpp" #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") #include using namespace std; struct __INIT__{__INIT__(){cin.tie(0);ios::sync_with_stdio(false);cout< vec; typedef vector> mat; typedef vector>> mat3; typedef vector svec; typedef vector> smat; templateusing V=vector; templateusing VV=V>; templateinline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<inline void output2(T t){for(auto i:t)output(i);} templateinline void debug(T t){bool f=0;for(auto i:t){cerr<<(f?" ":"")<inline void debug2(T t){for(auto i:t)output(i);} #define loop(n) for(long long _=0;_<(long long)(n);++_) #define rep(i,...) for(auto i:range(__VA_ARGS__)) #define rrep(i,...) for(auto i:reversed(range(__VA_ARGS__))) #define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i) #define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i) #define irep(i) for(lint i=0;;++i) inline vector range(long long n){if(n<=0)return vector();vectorv(n);iota(v.begin(),v.end(),0LL);return v;} inline vector range(long long a,long long b){if(b<=a)return vector();vectorv(b-a);iota(v.begin(),v.end(),a);return v;} inline vector range(long long a,long long b,long long c){if((b-a+c-1)/c<=0)return vector();vectorv((b-a+c-1)/c);for(int i=0;i<(int)v.size();++i)v[i]=i?v[i-1]+c:a;return v;} templateinline T reversed(T v){reverse(v.begin(),v.end());return v;} #define all(n) begin(n),end(n) templatebool chmin(T& s,const E& t){bool res=s>t;s=min(s,t);return res;} templatebool chmax(T& s,const E& t){bool res=s(s,t);return res;} const vector dx={1,0,-1,0,1,1,-1,-1}; const vector dy={0,1,0,-1,1,-1,1,-1}; #define SUM(v) accumulate(all(v),0LL) templateauto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector(arg,x);else return vector(arg,make_vector(x,args...));} #define extrep(v,...) for(auto v:__MAKE_MAT__({__VA_ARGS__})) vector> __MAKE_MAT__(vector v){if(v.empty())return vector>(1,vector());long long n=v.back();v.pop_back();vector> ret;vector> tmp=__MAKE_MAT__(v);for(auto e:tmp)for(long long i=0;iostream& operator<<(ostream& out,pairv){out<<"("<>; template using graph_w=std::vector>>; graph load_graph(int n,int m){graph g(n);for(int i=0;i>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_digraph(int n,int m){graph g(n);for(int i=0;i>s>>t;--s;--t;g[s].push_back(t);}return g;} graph load_graph0(int n,int m){graph g(n);for(int i=0;i>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_digraph0(int n,int m){graph g(n);for(int i=0;i>s>>t;g[s].push_back(t);}return g;} graph load_tree(int n){graph g(n);for(int i=0;i>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_tree0(int n){graph g(n);for(int i=0;i>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_treep(int n){graph g(n);for(int i=0;i>t;g[i+1].push_back(t);g[t].push_back(i+1);}return g;} templategraph_w load_graph_weight(int n,int m){graph_w g(n);for(int i=0;i>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} templategraph_w load_digraph_weight(int n,int m){graph_w g(n);for(int i=0;i>s>>t>>u;--s;--t;g[s].emplace_back(t,u);}return g;} templategraph_w load_graph0_weight(int n,int m){graph_w g(n);for(int i=0;i>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} templategraph_w load_digraph0_weight(int n,int m){graph_w g(n);for(int i=0;i>s>>t>>u;g[s].emplace_back(t,u);}return g;} templategraph_w load_tree_weight(int n){graph_w g(n);for(int i=0;i>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} templategraph_w load_tree0_weight(int n){graph_w g(n);for(int i=0;i>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} templategraph_w load_treep_weight(int n){graph_w g(n);for(int i=0;i>t>>u;g[i+1].emplace_back(t,u);g[t].emplace_back(i+1,u);}return g;} #line 4 "cpplib/graph_tree/lca_short.hpp" /** * @brief LCA(HL分解)&lt;O(N),O(logN)&gt; */ struct lca{ graph g; std::vectorsz,in,out,nxt,par,par2; lca(const graph& g,int s):g(g){ int n=g.size(); sz.resize(n,0); in.resize(n,0); out.resize(n,0); nxt.resize(n,s); par.resize(n,s); par2.resize(n,s); dfs_sz(s,-1); dfs_hld(s,-1); } void dfs_sz(int v,int p) { sz[v] = 1; for(auto &u: g[v]) { if(p==u)continue; dfs_sz(u,v); sz[v]+=sz[u]; if(sz[u]>sz[g[v][0]])std::swap(u,g[v][0]); } } void dfs_hld(int v,int p) { static int t=0; in[v]=t++; for(auto u: g[v]){ if(p==u)continue; nxt[u]=(u==g[v][0]?nxt[v]:u); par[u]=(u==g[v][0]?par[v]:v); par2[u]=v; dfs_hld(u,v); } out[v] = t; } int query(int s,int t){ while(nxt[s]!=nxt[t]){ if(sz[nxt[s]]>sz[nxt[t]])t=par[t]; else s=par[s]; } return sz[s]>sz[t]?s:t; } int distance(int s,int t){ int res=0; while(nxt[s]!=nxt[t]){ if(sz[nxt[s]]>sz[nxt[t]]){ res+=in[t]-in[nxt[t]]+1; t=par[t]; } else { res+=in[s]-in[nxt[s]]+1; s=par[s]; } } return res+std::abs(in[s]-in[t]); } std::vectorpath(int s,int t){ int l=query(s,t); vectorp,q; while(s!=l){ p.push_back(s); s=par2[s]; } while(t!=l){ q.push_back(t); t=par2[t]; } p.push_back(l); p.insert(p.end(),q.rbegin(),q.rend()); return p; } }; #line 3 "code.cpp" int main(){ lint n,q,c; cin>>n>>q>>c; vector> dist(n,vector(n,0)); vector> g(n); vector>>v(n); rep(i,n-1){ lint s,t,l; cin>>s>>t>>l; s--;t--; g[s].push_back(t); g[t].push_back(s); v[s].emplace_back(t,l); v[t].emplace_back(s,l); dist[s][t]=l; dist[t][s]=l; } lca lca(g,0); vectorx(q); rep(i,q)cin>>x[i]; vectorcnt(n,INF); cnt[x[0]-1]=0; lint cnt2=0; rep(i,q-1){ int s=x[i]-1,t=x[i+1]-1; auto d=lca.path(s,t); lint mn=*min_element(all(cnt)); rep(j,d.size()){ cnt[d[j]]=min(mn,cnt[d[j]]+c)-cnt2; chmin(mn,cnt[d[j]]+cnt2); if(j<(int)d.size()-1){ cnt2+=dist[d[j]][d[j+1]]; mn+=dist[d[j]][d[j+1]]; } // rep(k,n){ // cerr<