개미

개미집은 $n$개의 방으로 이루어져 있고, 각 방에는 1번부터 $n$번까지 번호가 붙어 있다. 그중 1번 방은 지면과 바로 이어진 방이다. 방들은 굴로 연결되어 있으며, 굴 하나를 지나가려면 그 굴의 길이만큼 에너지를 쓴다. 남은 에너지가 굴의 길이보다 적은 개미는 그 굴을 지나가지 못한다.

개미는 집짓기의 달인이라 쓸모없는 굴은 파지 않는다. 그래서 한 방에서 다른 방으로 가는 경로는 항상 있고, 그 경로는 하나뿐이다. 두 방 사이의 거리는 두 방을 잇는 경로에 놓인 굴의 길이를 모두 더한 값이다.

겨울잠에서 깬 개미들은 지면으로 올라가 햇살을 보고 싶어 한다. 그래서 지면과 이어진 1번 방으로 이동한다. 그런데 긴 겨울잠 탓에 모아 둔 에너지가 얼마 없어서, 1번 방에 닿기 전에 에너지를 다 써 버리기도 한다. 에너지가 0이 된 개미는 더 이상 움직이지 못한다. 1번 방에 도착한 개미도 그 자리에서 멈춘다.

지금 모든 방에 개미가 한 마리씩 있고, 개미마다 모아 둔 에너지가 있다. 잠에서 깬 개미는 모두 1번 방을 향해 이동한다. 각 개미가 도달할 수 있는 방 중에서 1번 방과 가장 가까운 방의 번호를 구하라.

첫째 줄에 방의 개수 $n$이 주어진다. ($1 \le n \le 10^5$)

다음 $n$개의 줄에는 각 방에 있는 개미의 에너지가 차례대로 주어진다. $i+1$번째 줄의 값은 $i$번 방에 있는 개미의 에너지이며, $10^5$ 이하의 자연수이다.

그다음 $n-1$개의 줄에는 굴 하나의 정보가 세 정수 $a$, $b$, $c$로 주어진다. $a$번 방과 $b$번 방이 굴로 이어져 있고, 그 굴의 길이가 $c$이다. 굴의 길이는 $10^4$ 이하의 자연수이다.

$n$개의 줄을 출력한다. $i$번째 줄에는 $i$번 방에 있던 개미가 도달할 수 있는 방 중에서 1번 방과 가장 가까운 방의 번호를 출력한다.