Орехус отправляется путешествовать в Древесную страну, в которой \(n\) городов. Кроме того, что большая часть её территории покрыта лесами, местная система дорог также представляет собой дерево (связный ациклический граф). Орехус хочет арендовать автомобиль в городе \(u\) и поехать по простому пути до города \(v\). Он ещё не определил свой путь, и сейчас самое время это сделать. Обратите внимание, что выбранный путь может состоять из одной вершины.
В \(i\)-м городе стоит бензоколонка, в которой по странным законам Древесной страны можно купить не более \(w_i\) литров бензина. Можно считать, что у Орехуса бесконечное количество денег. У каждой дороги есть длина, и как только Орехус проезжает по ней, количество бензина уменьшается на длину дороги. Конечно, Орехус не сможет поехать по пути, на одной из дорог которого ему не хватит бензина. Он может купить в бензин в любом городе, в котором он был, в том числе в первом и последнем.
Кроме того, он хочет найти максимальное количество бензина, которое у него может остаться в конце пути. Помогите ему: посчитайте это количество.
Выходные данные
Выведите одно число — максимальное количество бензина, которое может остаться у Орехуса в конце пути.
Примечание
Оптимальный путь в первом примере \(2 \to 1 \to 3\).
Оптимальный путь во втором примере \(2 \to 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 3 3
1 2 2
1 3 2
|
3
|
|
2
|
5
6 3 2 5 0
1 2 10
2 3 3
2 4 1
1 5 1
|
7
|