중복 없는 드라이브

JAG 왕국 사람들은 중복을 싫어한다. 예를 들어 왕국의 $N$개 도시는 정확히 $N-1$개의 양방향 도로로 연결되어 있고, 어느 도시에서든 도로를 따라 다른 모든 도시로 갈 수 있다. 이 조건에서는 어떤 두 도시 사이에도 경로가 정확히 하나뿐이다. 이것이 중복 없는 도로망이다.

어느 날 왕국의 시민인 당신은 차를 타고 가능한 한 많은 도시를 여행하기로 했다. 차의 연료 탱크는 무한히 크지만 처음에는 비어 있다. 차는 1 km를 달릴 때마다 휘발유 1리터를 소비한다.

각 도시에는 주유소가 정확히 하나 있고, 도시 $x$의 주유소에서는 휘발유 $g_x$리터를 넣을 수 있다. 여행 중 일부 주유소는 들르지 않아도 된다. 하지만 같은 주유소에서 두 번 이상 주유하는 것은 중복이므로 하지 않는다. 왕국의 각 도로에는 두 도시 사이의 거리가 정해져 있고, $i$번째 도로의 거리는 $d_i$ km이다. 같은 도시나 같은 도로를 두 번 이상 지나는 것도 당연히 중복이므로 하지 않는다.

남은 휘발유가 0이 되면 차는 움직일 수 없고, 여행은 거기서 끝난다. 처음에 탱크가 비어 있는 것은 걱정하지 않아도 된다. 왕국의 어느 도시에서든 그 도시의 주유소에서 여행을 시작할 수 있다. 또한 각 도로는 양 끝 도시의 주유소를 직접 연결하므로 (중복을 피하는 정신은 도시 안에서의 불필요한 이동도 피한다), 도시에 도착하는 순간 탱크가 정확히 비더라도 그 도시에서 주유할 수 있다.

이 중복 없는 원칙을 지키면서 여행할 수 있는 도시 수의 최댓값을 구하는 프로그램을 작성하시오.

입력은 하나의 테스트 케이스로 이루어진다.

N
g1 ... gN
a1 b1 d1
...
aN-1 bN-1 dN-1

첫째 줄에 왕국의 도시 수 $N$ ($1 \le N \le 100000$)이 주어진다. 둘째 줄에 $N$개의 정수가 주어지며, 그중 $i$번째 정수 $g_i$ ($1 \le g_i \le 10000$)는 도시 $i$의 주유소에서 넣을 수 있는 휘발유의 양이다. 다음 $N-1$개 줄에 도로 정보가 주어진다. 그중 $j$번째 줄에는 $a_j$, $b_j$, $d_j$가 주어지며, 이는 $j$번째 도로가 도시 $a_j$와 도시 $b_j$ ($1 \le a_j, b_j \le N$, $a_j \ne b_j$)를 거리 $d_j$ ($1 \le d_j \le 10000$)로 양방향 연결한다는 뜻이다. 왕국의 모든 도시는 도로로 연결되어 있다.

주유소마다 최대 한 번만 주유한다는 제약 아래에서, 어느 도시에서 출발하든 상관없이 여행할 수 있는 도시 수의 최댓값을 출력한다.