Берляндия состоит из $$$n$$$ городов, некоторые из которых соединены двусторонними дорогами таким образом, что между каждой парой вершин существует ровно один путь, проходящий по каждой дороге не более одного раза. Каждая дорога характеризуется своей длиной. Города пронумерованы от $$$1$$$ до $$$n$$$.
Время пути между некоторыми городами $$$v$$$ и $$$u$$$ — это суммарная длина дорог на кратчайшем пути из $$$v$$$ в $$$u$$$.
Два наиболее важных города Берляндии имеют номера $$$1$$$ и $$$n$$$.
Министерство Транспорта Берляндии решило построить ровно одну новую дорогу, чтобы разгрузить движение между самыми важными городами. Однако многие уже привыкли к текущему времени пути между самыми важными городами, поэтому новая дорога не должна его сильно изменить.
Новая дорога может быть построена только между такими городами $$$v$$$ и $$$u$$$, что $$$v \neq u$$$ и $$$v$$$ и $$$u$$$ еще не соединены никакой дорогой.
Они создали планы $$$m$$$ возможных проектов. Каждый проект — это просто длина $$$x$$$ новой дороги.
Поликарп работает главным аналитиком Министерства Транспорта Берляндии, разбираться с этими $$$m$$$ проектами — его задача. Для $$$i$$$-го проекта он должен выбрать некоторые города $$$v$$$ и $$$u$$$ и построить новую дорогу длины $$$x_i$$$ между ними так, чтобы время пути между самыми важными городами было максимально возможным.
К сожалению, Поликарп совсем не программист, да и никакой аналитик в мире не справится со всеми проектами с помощью лишь ручки и бумаги.
Поэтому он просит вас помочь ему посчитать максимально возможное время пути между самыми важными городами для каждого проекта. Обратите внимание, что $$$v$$$ и $$$u$$$ выбираются независимо для каждого проекта.
В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 3 \cdot 10^5$$$) — количество городов и количество проектов, соответственно.
В каждой из следующих $$$n - 1$$$ строк записаны по три целых числа $$$v_i$$$, $$$u_i$$$ и $$$w_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$1 \le w_i \le 10^9$$$) — описание $$$i$$$-й дороги. Гарантируется, что между каждой парой городов существует ровно один путь, проходящий по каждой дороге не более одного раза.
В каждой из следующих $$$m$$$ строк записано по одному целому числу $$$x_j$$$ ($$$1 \le x_j \le 10^9$$$) — длина дороги для $$$j$$$-го проекта.
Выведите $$$m$$$ строк, $$$j$$$-я строка должна содержать одно целое число — максимально возможное время пути между самыми важными городами для $$$j$$$-го проекта.
7 2
1 2 18
2 3 22
3 4 24
4 7 24
2 6 4
3 5 12
1
100
83
88
Сеть дорог из первого примера:
Можно построить дорогу длины $$$1$$$ между городами $$$5$$$ и $$$6$$$, чтобы получить $$$83$$$ в качестве времени пути между $$$1$$$ и $$$7$$$ ($$$1 \rightarrow 2 \rightarrow 6 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 7$$$ $$$=$$$ $$$18 + 4 + 1 + 12 + 24 + 24 = 83$$$). Другие доступные пары городов дадут ответ меньше или равный $$$83$$$.
