import sys from collections import deque def main(): sys.setrecursionlimit(1 << 25) N, Q, C = map(int, sys.stdin.readline().split()) edges = [[] for _ in range(N+1)] for _ in range(N-1): u, v, l = map(int, sys.stdin.readline().split()) edges[u].append((v, l)) edges[v].append((u, l)) x = list(map(int, sys.stdin.readline().split())) # Precompute distance between all pairs using BFS for each node dist = [[-1] * (N+1) for _ in range(N+1)] for s in range(1, N+1): q = deque() q.append(s) dist[s][s] = 0 while q: u = q.popleft() for v, l in edges[u]: if dist[s][v] == -1: dist[s][v] = dist[s][u] + l q.append(v) # Precompute the path for each x[i] to x[i+1] # For each query, find the path from a to b # To find the path, use BFS and track parents def get_path(a, b): parent = [-1] * (N+1) q = deque() q.append(a) parent[a] = None while q: u = q.popleft() if u == b: break for v, l in edges[u]: if parent[v] == -1: parent[v] = u q.append(v) path = [] u = b while u is not None: path.append(u) u = parent[u] return path[::-1] # Initialize DP dp = [dict() for _ in range(Q)] # dp[i][b] = min time to reach x[i] with beacon at b (b=0 means no beacon) dp[0][0] = 0 for i in range(Q-1): current = x[i] next_node = x[i+1] path = get_path(current, next_node) path_set = set(path) current_dp = dp[i] next_dp = {} for prev_b in current_dp: current_time = current_dp[prev_b] # Option 1: Move normally, beacon remains prev_b (if exists) time_normal = dist[current][next_node] key = prev_b if key not in next_dp or current_time + time_normal < next_dp[key]: next_dp[key] = current_time + time_normal # Option 2: If there's a beacon, jump to it and then move if prev_b != 0: time_jump = C + dist[prev_b][next_node] key = 0 if key not in next_dp or current_time + time_jump < next_dp[key]: next_dp[key] = current_time + time_jump # Option 3: Place beacon at some node on the path for a in path: time_place = dist[current][a] + dist[a][next_node] key = a new_time = current_time + time_place if key not in next_dp or new_time < next_dp[key]: next_dp[key] = new_time # Option 4: If there's a beacon, jump to it, then place beacon on path if prev_b != 0: for a in path: time_jump_place = C + dist[prev_b][a] + dist[a][next_node] key = a new_time = current_time + time_jump_place if key not in next_dp or new_time < next_dp[key]: next_dp[key] = new_time dp[i+1] = next_dp # The answer is the minimum value in dp[Q-1] print(min(dp[Q-1].values())) if __name__ == '__main__': main()