Less Travel

mubtasim91 Ada Lovelace National Gir...
Limits 1s, 512 MB

NishatNishat loves travelling a lot. Currently she is in a newly independent country named NewKalyNewKaly (previously which was a district of Bangladesh).

She decided to visit each of the nn cities of NewKaly at least once with smallest possible traverse. 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 11 to nn. Among these Nishat has qq distinct favorite cities. She wants to select one of these qq cities and wish to visit all other cities with minimum possible traverse. 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 qq cities? After that she would decide which city she would select finally.


First line contains two space separated positive integers nn and qq (2n200000,1qn)(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 qq space separated distinct positive integers c1c_1, c2c_2, c3c_3,..., cqc_q (1cin,1iq)(1 \le c_i \le n, 1 \le i \le q) - Nishat's favorite cities.

Next n1n - 1 lines contain three space separated positive integers xix_i, yiy_i and wiw_i (1xi,yin,1w106,1in1)(1 \le x_i, y_i \le n, 1 \le w \le 10^6, 1 \le i \le n-1) - xix_i and yiy_i are two cities which are connected by a road and wiw_i is the length of that road.


In a single line print qq space separated integers d1d_1, d2d_2, d3d_3,..., dqd_q- minimum possible traverse needed from each of the c1c_1, c2c_2, c3c_3,..., cqc_q cities respectively.


4 4
3 1 2 4
1 2 3
2 3 4
4 2 7
17 18 21 17
3 2
3 1
1 2 3
2 3 4
7 7


Login to submit.


100% Solution Ratio
sakib_muhitEarliest, 2M ago
steinumFastest, 0.0s
IU_SpiralForgeLightest, 24 kB
The_LastPhaseShortest, 1008B
Toph uses cookies. By continuing you agree to our Cookie Policy.