F1. Экспедиция (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии нужно завершить путь в начальной пещере.

Генри отправился в экспедицию в сеть пещер за древними артефактами. Вход в пещеры находится в вершине $$$1$$$, а коридоры между пещерами образуют дерево.

Генри освещает путь магической лампой. Для прохождения $$$i$$$-го коридора лампа расходует $$$w_i$$$ единиц заряда при каждом прохождении.

Однако коридоры пещер крайне неустойчивы. После двух прохождений по одному и тому же коридору его своды становятся слишком хрупкими, и в третий раз воспользоваться этим коридором уже невозможно. Поэтому Генри может пройти по каждому коридору не более двух раз, независимо от направления движения.

В каждой пещере находится артефакт. При первом посещении вершины $$$v$$$ артефакт изменяет заряд лампы на $$$a_v$$$ единиц: некоторые артефакты восстанавливают заряд (для которых $$$a_v \gt 0$$$), а другие оказываются проклятыми и, наоборот, забирают его ($$$a_v \lt 0$$$). Повторное посещение пещеры больше не влияет на заряд лампы.

В начале экспедиции Генри находится в пещере $$$1$$$ и сразу активирует находящийся в ней артефакт. Заряд лампы ни в какой момент не должен становиться отрицательным.

Генри должен посетить все пещеры и собрать все артефакты. После этого он должен вернуться в пещеру $$$1$$$ и покинуть подземелье.

Определите минимальный начальный заряд лампы, с которым Генри сможет завершить экспедицию.

Входные данные

В первой строке входных данных содержится одно целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — количество пещер.

Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ — изменения заряда лампы после первого посещения соответствующих пещер. Обратите внимание, что каждый коридор можно пройти не более двух раз вне зависимости от направления движения.

В следующих $$$n - 1$$$ строках содержатся по три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ $$$(1 \le u_i, v_i \le n,\ u_i \ne v_i,\ 1 \le w_i \le 10^9)$$$ — концы $$$i$$$-го коридора и количество заряда, необходимое для его прохождения.

Гарантируется, что коридоры образуют дерево.

Выходные данные

В единственной строке выведите одно целое число — минимальный начальный заряд лампы, с которым Генри сможет посетить все пещеры, не допуская отрицательного заряда лампы.

Примеры
Входные данные
5
1 10 -2 6 7
1 2 10
1 3 2
3 4 1
3 5 7
Выходные данные
18
Входные данные
4
2 -90 15 30
1 2 4
2 3 5
1 4 10
Выходные данные
87