Задача: Сигнализация

Подземный бункер состоит из \(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\)).

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

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

Ваш ответ: