왕실 세금

Nlogônia 왕국은 부유하고 백성은 배울 만큼 배웠으며 살림도 넉넉하지만, 세금 문제에서만큼은 왕이 가혹하다. 해마다 연말이 되면 왕국의 각 도시는 정해진 양의 금을 세금으로 내야 한다. 세금을 걷을 때가 되면 왕은 왕실 마차를 보내 왕국의 도로를 따라 내야 할 금을 거둬들인다.

각 도로는 서로 다른 두 도시를 잇고 양쪽 방향으로 다닐 수 있다. 도로망은 어느 도시에서 어느 도시로든 (중간 도시를 거쳐서라도) 갈 수 있게 이어져 있고, 서로 다른 두 도시를 잇는 경로는 하나뿐이다.

모든 도시에는 세금으로 걷은 금을 보관하는 왕실 금고가 하나씩 있다. 금고는 대단히 커서 왕국 전체가 내야 할 금을 전부 넣어도 자리가 남는다. 마차는 수도에서 출발해 도로를 따라 도시를 돌며 그 도시가 내야 할 금을 싣는다. 필요하면 이미 걷은 금의 일부를 아무 왕실 금고에나 잠시 맡겨 둘 수 있다. 수거가 끝난 시점에는 모든 도시가 낸 금이 전부 수도의 금고에 있어야 한다.

각 도시가 내야 할 금의 양(kg), 도로의 목록과 각 도로의 길이(km), 왕실 마차의 적재 용량(kg)이 주어진다. 마차가 내야 할 금을 모두 거두려면 최소 몇 km를 달려야 하는지 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 수 $N$과 마차의 적재 용량 $C$가 주어진다 ($2 \le N \le 10^4$, $1 \le C \le 100$). 수도는 1번 도시이고 나머지 도시에는 2번부터 $N$번까지 번호가 붙는다.

둘째 줄에 $N$개의 정수 $E_1, E_2, \dots, E_N$이 주어진다. $E_i$는 $i$번 도시가 내야 할 금의 양이며 단위는 kg이다 ($0 \le E_i \le 100$).

이어지는 $N-1$개의 줄에 각각 세 정수 $A$, $B$, $L$이 주어진다. 이는 $A$번 도시와 $B$번 도시를 잇는 길이 $L$ km의 도로가 있다는 뜻이다 ($1 \le A, B \le N$, $A \ne B$, $1 \le L \le 100$).

마차가 내야 할 금을 모두 거두기 위해 달려야 하는 최소 거리를 km 단위 정수 하나로 첫째 줄에 출력한다.