General Mobilization

The Berland Kingdom은 n - 1개의 철도로 서로 연결된 n개의 도시로 이루어진 집합이다. 각 도로는 정확히 서로 다른 두 도시를 연결한다. 수도는 도시 1에 있다. 각 도시에서 철도를 통해 수도로 갈 수 있는 경로가 존재한다.

i-th번째 도시에는 번호가 i인 병사 사단이 있으며, 각 사단은 ai라는 수로 특징지어진다. 이 수는 우선순위를 나타내며, 수가 작을수록 해당 사단의 우선순위가 높다. 모든 ai의 값은 서로 다르다.

어느 날 Berland King Berl Great은 총동원령을 선포했고, 이에 따라 각 사단은 수도에 도착해야 한다. 매일 수도를 제외한 모든 도시에서 열차 한 대가 출발한다. 따라서 매일 출발하는 열차는 정확히 n - 1대이다. 각 열차는 수도를 향해 이동하며, 다음 날 철도의 반대쪽 끝점에서 이동을 마친다. 열차에는 한 번에 운송할 수 있는 사단 수의 최댓값으로 표현되는 유한한 수용량 cj이 있다. 각 열차는 수도까지의 거리가 줄어드는 방향으로 이동한다. 따라서 각 열차는 한 도시에서 수도 방향에 있는 인접 도시(열차가 정차하는 곳)로 이동하면서 정확히 하나의 철도를 지난다.

도시에 있는 사단들 가운데 ai가 가장 작은 사단이 가장 먼저 열차에 타고, 그다음으로 작은 사단이 타는 식으로 열차가 가득 차거나 모든 사단이 탑승할 때까지 계속된다. 따라서 사단이 한 도시에 며칠 동안 머무를 수도 있다.

열차가 한 도시에서 다른 도시로 이동하는 데 걸리는 시간은 항상 1일이다. 모든 사단은 동시에 이동을 시작하여 수도에 도착하며, 그곳에 도착한 뒤에는 더 이상 어디로도 이동하지 않는다. 각 사단은 이 여정에 걸리는 시간과 관계없이 자신의 도시에서 수도까지 단순 경로를 따라 이동한다.

각 사단이 Berland의 수도에 며칠 만에 도착하는지 구하는 것이 목표이다. 날짜는 day 0부터 센다.

첫 번째 줄에는 하나의 정수 n (1 ≤ n ≤ 5000)이 주어진다. 이는 Berland의 도시 수이다. 두 번째 줄에는 공백으로 구분된 정수 n개 a1, a2, ..., an이 주어지며, ai는 도시 번호 i에 위치한 사단의 우선순위를 나타낸다. 모든 수 a1, a2, ..., an은 서로 다르다 (1 ≤ ai ≤ 109). 이어지는 n - 1개의 줄에는 철도에 대한 설명이 주어진다. 각 설명은 세 정수 vj, uj, cj로 이루어지며, vj, uj는 j-th번째 철도로 연결된 도시의 번호이고, cj는 이 철도를 운행하는 열차의 최대 수용량을 나타낸다 (1 ≤ vj, uj ≤ n, vj ≠ uj, 1 ≤ cj ≤ n).

수열 t1, t2, ..., tn을 출력한다. 여기서 ti는 도시 i의 사단이 수도에 도착하는 데 걸리는 일수를 나타낸다. 수들은 공백으로 구분한다.