Сигнализация

Подземный бункер состоит из $n$ комнат, соединённых $n - 1$ коридорами. Каждый коридор соединяет две различные комнаты и имеет определённую длину. Бункер устроен таким образом, что из любой комнаты $i$ можно дойти в любую другую комнату $j$. Заметим, что существует единственный такой путь, не проходящий по одному и тому же коридору дважды. Сумма длин коридоров, составляющих этот путь, называется расстоянием между комнатами $i$ и $j$ и обозначается $\rho(i, j)$.

Каждая комната бункера оборудована звуковой сигнализацией, состоящей из сирены и датчика звука, который её включает. Сирена, включённая в комнате $i$, активирует датчик звука в каждой комнате, расстояние до которой не превосходит расстояние $d\_i$, определяемое мощностью этой сирены. Другими словами, включение сирены в комнате $i$ автоматически включает сирену во всех комнатах $j$, таких что $\rho(i, j) \leq d\_i$. Эта сирена, в свою очередь, может вызвать автоматическое включение других сирен и так далее.

В случае возникновения чрезвычайной ситуации некоторые сирены необходимо включить вручную, после чего звук от них автоматически включит сирены в других комнатах. Правила безопасности предписывают выбор такого набора сирен для ручного включения, который в конце концов приведёт к автоматическому включению сирен во всех комнатах.

Требуется написать программу, которая определяет минимальное количество сирен в наборе, удовлетворяющем правилам безопасности.

Первая строка входных данных содержит единственное число $n$ --- количество комнат.

Вторая строка содержит последовательность из $n$ целых чисел $d\_i$, $i$-е из них равно максимальному расстоянию, на котором расположенная в комнате $i$ сирена активирует датчики ($0 \leq d\_i \leq 10^9$).

Последующие $n - 1$ строк описывают коридоры бункера. В $i$-й из них находятся три целых числа: $u\_i$, $v\_i$, $l\_i$, где $u\_i$, $v\_i$ --- номера различных комнат, соединённых коридором $i$, а $l\_i$ --- длина этого коридора ($1 \leq u\_i, v\_i \leq n$; $1 \leq l\_i \leq 10^9$).

Выходные данные должны состоять из единственного числа --- минимального количества сирен, которые необходимо включить вручную.

• $1 \leq n \leq 300\\,000$

В тесте из примера сирена в комнате 4 включает сирену в комнате 5, которая, в свою очередь, включает сирены в комнатах 6 и 7. Сирена в комнате 2 включает сирену в комнате 3. Сирена в комнате 8 включает сирены в комнатах 1, 9 и 10.