It's Christmas! Santa has joined the World Health Organization. Being in the middle of a pandemic, Santa will need to use his delivery skills to deliver vaccines instead of presents.
Being the genius he is, he developed a system called T.M.A.S
(TMAS: Modern Accelerated Sender) that can deliver vaccines through a distributed network of cities at great speeds!
The T.M.A.S
network of the world is represented as a tree with cities and bi-directional routes that Santa can take. In fact, each connection between two cities and will be kilometers in length. To test the effectiveness of this system, Santa decides to send vaccines as far as possible from a given node.
He will give you cities. For each city, find the furthest distance away from the city that he can send the vaccine.
Input Specification
The first line contains two integers and , the number of cities and the number of queries respectively.
Each of the next lines contains three integers and indicating a bi-directional connection between and with distance .
Each of the next lines will contain a city for which you must print the furthest distance away from this city.
For of the test cases and .
Output Specification
For each in the given query, print the furthest distance that Santa is able to achieve.
Sample Input
6 3
2 1 4
6 3 1
4 3 5
3 2 2
5 3 2
3
2
1
Sample Output
6
7
11
Explanation
For city the furthest city away is with a distance of .
For city the furthest city away is with a distance of .
For city the furthest city away is with a distance of .
Comments