#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; typedef unsigned int ui; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=sta;i--) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LP; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; templatebool chmax(T &a, const T &b) {if(abool chmin(T &a, const T &b) {if(b> D,G; vector depth; void dfs(int s,int par){ D[s].push_back(par); if (par!=-1) depth[s]=depth[par]+1; rep(i,G[s].size()){ int t=G[s][i]; if (t==par) continue; dfs(t,s); } } LCA(int n_,int r_){ n=n_;root=r_; depth.resize(n,0); D.resize(n,{}); G.resize(n,{}); } void add_edge(int a,int b){ G[a].push_back(b); G[b].push_back(a); } void build(){ dfs(root,-1); while(true){ bool flag=false; int m=(1< G[3010]; ll depth[3010],d[3010][3010]; ll dp[3010][3010]; int x[3010]; void dfs_(int s,int par,ll l){ if(par!=-1)depth[s]=depth[par]+l; for(edge e:G[s]){ if(e.to==par) continue; dfs_(e.to,s,e.l); } } pair dfs(int i,int s,int par){ dp[i+1][s]=dp[i][s]+d[x[i]][x[i+1]]; bool flag=false;ll z=INF; if(s==x[i]) flag=true; for(edge e:G[s]){ if(e.to==par) continue; auto pai=dfs(i,e.to,s); if(pai.second) flag=true; chmin(z,pai.first); } chmin(z,dp[i][s]+c+d[s][x[i+1]]); if(flag){ chmin(dp[i+1][s],dp[i][x[i]]+d[x[i]][x[i+1]]); chmin(dp[i+1][s],z); } else{ chmin(dp[i+1][s],z); } return pair(z,flag); } void solve(){ cin >> n >> q >> c; LCA lca(n,0); rep(i,n-1){ int a,b,l;cin >> a >> b >> l;a--;b--; lca.add_edge(a,b); G[a].push_back({b,l}); G[b].push_back({a,l}); } rep(i,q) { cin >> x[i];x[i]--; } dfs_(0,-1,0); lca.build(); rep(i,n){ rep(j,i){ d[i][j]=depth[i]+depth[j]-2ll*depth[lca.lca(i,j)]; d[j][i]=d[i][j]; //cout << i << " " << j << " " << d[i][j] << endl; } } rep(i,n) dp[0][i]=INF; dp[0][x[0]]=0; rep(i,q-1){ dfs(i,x[i+1],-1); // rep(j,n){ // cout << i+1 << " " << j << " " << dp[i+1][j] << endl; // } } ll ans=INF; rep(i,n){ chmin(ans,dp[q-1][i]); } cout << ans << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }