import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } enum E = 13; enum INF = 10L^^18; int N, Q; long C; int[] A, B; long[] L; int[] X; int[][] G; long[] dep; int[] poss; alias Entry = Tuple!(long, "d", int, "u"); Entry[] es; void dfs(int u, int p, long d) { dep[u] = d; poss[u] = cast(int)(es.length); es ~= Entry(d, u); foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; if (v != p) { dfs(v, u, d + L[i]); es ~= Entry(d, u); } } } int esLen; Entry[][] mns; int lca(int u, int v) { int a = poss[u], b = poss[v]; if (a > b) { swap(a, b); } const e = bsr(b - a + 1); const l = min(mns[e][a], mns[e][b + 1 - (1 << e)]).u; debug { // writefln("lca %s %s = %s", u, v, l); } return l; } void main() { try { for (; ; ) { N = readInt(); Q = readInt(); C = readLong(); A = new int[N - 1]; B = new int[N - 1]; L = new long[N - 1]; foreach (i; 0 .. N - 1) { A[i] = readInt() - 1; B[i] = readInt() - 1; L[i] = readLong(); } X = new int[Q]; foreach (q; 0 .. Q) { X[q] = readInt() - 1; } G = new int[][N]; foreach (i; 0 .. N - 1) { G[A[i]] ~= i; G[B[i]] ~= i; } dep = new long[N]; poss = new int[N]; es = []; dfs(0, -1, 0); esLen = cast(int)(es.length); mns = new Entry[][](E, esLen); mns[0][] = es[]; foreach (e; 0 .. E - 1) { mns[e + 1][] = mns[e][]; foreach (a; 0 .. esLen) { if (a + (1 << e) < esLen) { chmin(mns[e + 1][a], mns[e][a + (1 << e)]); } } } auto lcas = new int[][](N, N); auto dist = new long[][](N, N); foreach (u; 0 .. N) foreach (v; u .. N) { const l = lca(u, v); lcas[u][v] = lcas[v][u] = l; dist[u][v] = dist[v][u] = dep[u] + dep[v] - 2 * dep[l]; } foreach(i;0..N-1)if(dist[A[i]][B[i]]!=L[i])assert(false); foreach(w;0..N)foreach(u;0..N)foreach(v;0..N)if(dist[u][v]>dist[u][w]+dist[w][v])assert(false); auto ds = new long[Q - 1]; auto dsSum = new long[Q]; foreach (q; 0 .. Q - 1) { ds[q] = dist[X[q]][X[q + 1]]; dsSum[q + 1] = dsSum[q] + ds[q]; } debug { writeln("ds = ", ds); } auto dp = new long[Q]; dp[] = INF; dp[0] = 0; foreach (q; 0 .. Q - 1) { chmin(dp[q + 1], dp[q] + ds[q]); foreach (r; q + 2 .. Q) { int[3] us = [X[q], X[q + 1], X[r]]; int l; foreach (j; 0 .. 3) { l ^= lca(us[(j + 1) % 3], us[(j + 2) % 3]); } long cost = dp[q]; cost += dsSum[r - 1] - dsSum[q + 1]; foreach (j; 0 .. 3) { cost += dist[l][us[j]]; } cost += C; debug { writeln(q, " ", r, ": ", us, " ", l, " ", cost); } chmin(dp[r], cost); } } debug { writeln("dp = ", dp); } writeln(dp[Q - 1]); } } catch (EOFException e) { } }