Nishat loves traveling a lot. Currently she is in a newly independent country named NewKaly.
She decided to visit each of the 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 . Among these Nishat has distinct favorite cities. She wants to select one of these 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 cities? After that she would decide which city she would select finally.
First line contains two space separated positive integers and () --- the number of cities and the number of Nishat's favorite cities respectively.
Second line contains space separated distinct positive integers , , ,..., () - Nishat's favorite cities.
Next lines contain three space separated positive integers , and () - and are two cities which are connected by a road and is the length of that road.
In a single line print space separated integers , , ,..., - minimum possible traverse needed from each of the , , ,..., 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 |