14942번 - 개미

개미집은 n개의 방으로 구성되어 있으며 n개의 방은 1번부터 n번 까지 번호가 부여되어 있다. 그 중에서 1번 방은 지면에 바로 연결되어 있는 방이다. 각 방들은 서로 굴을 통해 연결되어 있다. 각 굴을 이동하기 위해서는 굴의 길이만큼 에너지가 소모된다.

개미는 집짓기의 달인이기 때문에 불필요한 굴은 짓지 않는다. 그래서 굴을 타고 한 방에서 다른 방으로 갈 수 있는 경로는 항상 존재하며 유일하다. 임의의 두 방 사이의 거리는 두 개의 방을 연결하는 경로를 구성하는 굴의 길이의 합이다.

겨울잠을 자던 개미들은 겨울잠에서 깨어나 지면으로 올라가 햇살을 보고 싶어한다. 그렇기 때문에 지면과 연결된 1번 방으로 이동을 하려고 한다. 하지만 불행하게도 개미는 긴 겨울잠을 자느라 축적해 놓은 에너지가 적다. 그래서 개미는 에너지를 1번 방에 도달하기 전에 모두 소모 할 수도 있다. 이렇게 에너지가 0이 된 개미는 더 이상 움직일 수 없다. 또한 1번 방에 도착한 개미는 더 이상 움직이지 않는다.

현재 모든 방에는 개미가 한 마리씩 있고 각각의 개미는 각자 축적된 에너지를 가지고 있다. 잠에서 깨어난 모든 개미는 1번 방을 향해서 이동한다. 이때 각각의 개미에 대해 도달할 수 있는 방 중에서 가장 1번 방에 가까운 방의 번호를 출력하시오.

자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 10⁵) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너지를 나타내는 100,000이하의 자연수 값이 주어진다. 이후 n-1개의 줄에는 두 개의 방을 연결하는 굴의 정보가 3개의 정수 a b c 으로 주어진다. a, b는 연결된 방을 의미하고 c는 이 굴의 길이를 의미한다. 굴의 길이는 10,000 이하의 자연수이다.

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