Hide

Problem G
Kamp

In a certain flooded village, a secret superhuman humanitarian camp is being opened as we speak. The village consists of $N$ houses marked with integers from $1$ to $N$. The houses are connected to each other with $N-1$ roads so that there is a unique way between each two houses. For each road, we know the time it takes for a truck to pass it. The camp should be put up in some house’s garden, but the camp manager still hasn’t decided which house it is going to be.

Mirko has been appointed as the driver. His job is to drive around teams of volunteers in his super truck from the camp to the house where that certain team is going to work. His truck is super because all teams at once can drive in it! In total, there are $K$ teams and all the teams are going to a different house.

All $K$ teams board into Mirko’s truck initially, and then he drives them to houses in the sequence he determined for himself. After he drives around all teams, Mirko stays and helps the last team (he doesn’t go back to camp).

In order for the camp manager to determine where to put up the camp, he wants to know, for each house, the minimal time it takes for Mirko to drive around all teams if that house is the headquarters. Write a program that will determine the numbers Mirko’s boss wants to see!

Input

The first line of input contains the integers $N$ ($1 \leq N \leq 500\, 000$), and $K$ ($1 \leq K \leq N$).

Each of the following $N-1$ lines contains integers $A_ i$, $B_ i$, $C_ i$ ($1 \leq A_ i, B_ i \leq N$, $1 \leq C_ i \leq 1\, 000\, 000$), where $C_ i$ is the time it takes to pass a two-way road between houses $A_ i$ and $B_ i$.

Each of the following $K$ lines contains and integer that marks the house where the $i$-th team is going, respectively.

Output

Output $N$ lines. The $i$-th line of output must contain the minimal times it takes Mirko to drive around all the teams if the camp headquarters is located in the $i$-th house.

Sample Input 1 Sample Output 1
5 2
2 5 1
2 4 1
1 2 2
1 3 2
4
5
5
3
7
2
2
Sample Input 2 Sample Output 2
7 2
1 2 4
1 3 1
2 5 1
2 4 2
4 7 3
4 6 2
3
7
11
15
10
13
16
15
10

Please log in to submit a solution to this problem

Log in