Nishat loves traveling a lot. Currently she is in a newly independent country named NewKaly.
She decided to visit each of the $n$ cities of NewKaly at least once with smallest possible traversal. Cities of NewKaly are connected with bidirectional roads. You can go from any city to any other one using these roads and there is a unique path between each two cities.
All cities are numbered from 1 to $n$. Among these Nishat has $q$ distinct favorite cities. She wants to select one of these $q$ cities and wish to visit all other cities with minimum possible traversal. She can finish her travel in any city.
Can you help Nishat to find out how much she would have to travel for each of these $q$ cities? After that she would decide which city she would select finally.
First line contains two space separated positive integers $n$ and $q$ ($2 \le n \le 200000, 1 \le q \le n$) --- the number of cities and the number of Nishat's favorite cities respectively.
Second line contains $q$ space separated distinct positive integers $c_1$, $c_2$, $c_3$,..., $c_q$ ($1 \le c_i \le n, 1 \le i \le q$) - Nishat's favorite cities.
Next $n - 1$ lines contain three space separated positive integers $x_i$, $y_i$ and $w_i$ ($1 \le x_i, y_i \le n, 1 \le w \le 10^6, 1 \le i \le n-1$) - $x_i$ and $y_i$ are two cities which are connected by a road and $w_i$ is the length of that road.
In a single line print $q$ space separated integers $d_1$, $d_2$, $d_3$,..., $d_q$- minimum possible traverse needed from each of the $c_1$, $c_2$, $c_3$,..., $c_q$ cities respectively.
Input | Output |
---|---|
4 4 3 1 2 4 1 2 3 2 3 4 4 2 7 | 17 18 21 17 |
Input | Output |
---|---|
3 2 3 1 1 2 3 2 3 4 | 7 7 |