Tree Party Delivery

You are given a tree with n nodes and n-1 edges. Each edge has an associated travel time. The tree is connected. There are K persons, each living at a distinct node (their home). They plan to have a party at some meeting point. After the party, a car starting at that meeting point must deliver each of the K persons back to their home. The car can traverse the tree arbitrarily and the route does not need to return to the meeting point.

For each vertex i (from 1 to n), if the party is held at vertex i, determine the minimal total time the driver needs to deliver all K people to their homes.

Note: It is optimal to first drive from the meeting point to the nearest node in the minimal subtree (also called the Steiner tree) that connects all special nodes (homes), then cover the subtree in an optimal route. In a tree the optimal route to cover a subtree starting at some node p is
2 × (sum of weights of all edges in the subtree) − (the maximum distance from p to any special node in the subtree).

Thus, if we let W be the sum of weights of the Steiner tree connecting the homes, and for any vertex i, let d(i) be the distance from i to the Steiner tree (0 if i is already in it) and let f(p) be the maximum distance from a Steiner tree node p (the one closest to i) to any home, then the answer for vertex i is:

[ answer[i] = 2\times W + d(i) - f(p) ]

where p is the closest node in the Steiner tree to vertex i.

inputFormat

The first line contains two integers n and K (1 ≤ K ≤ n) representing the number of nodes and the number of persons, respectively. The next n − 1 lines each contain three integers u, v, and w indicating that there is an edge between node u and node v with travel time w (w > 0). The last line contains K distinct integers representing the nodes where the persons live.

Input Format Summary:
Line 1: n K
Next n-1 lines: u v w
Last line: K distinct integers (special nodes)

outputFormat

Print a single line containing n space‐separated integers. The ith integer represents the minimal total time required if the party is held at node i.

sample

5 2
1 2 3
2 3 1
2 4 2
1 5 4
3 5

12 9 8 11 8