Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. General Mobilization

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe Berland Kingdom is a set of *n* cities connected with each other with *n* - 1 railways. Each road connects exactly two different cities. The capital is located in city 1. For each city there is a way to get from there to the capital by rail.

In the *i*-th city there is a soldier division number *i*, each division is characterized by a number of *a*_{i}. It represents the priority, the smaller the number, the higher the priority of this division. All values of *a*_{i} are different.

One day the Berland King Berl Great declared a general mobilization, and for that, each division should arrive in the capital. Every day from every city except the capital a train departs. So there are exactly *n* - 1 departing trains each day. Each train moves toward the capital and finishes movement on the opposite endpoint of the railway on the next day. It has some finite capacity of *c*_{j}, expressed in the maximum number of divisions, which this train can transport in one go. Each train moves in the direction of reducing the distance to the capital. So each train passes exactly one railway moving from a city to the neighboring (where it stops) toward the capital.

In the first place among the divisions that are in the city, division with the smallest number of *a*_{i} get on the train, then with the next smallest and so on, until either the train is full or all the divisions are be loaded. So it is possible for a division to stay in a city for a several days.

The duration of train's progress from one city to another is always equal to 1 day. All divisions start moving at the same time and end up in the capital, from where they don't go anywhere else any more. Each division moves along a simple path from its city to the capital, regardless of how much time this journey will take.

Your goal is to find for each division, in how many days it will arrive to the capital of Berland. The countdown begins from day 0.

Input

The first line contains the single integer *n* (1 ≤ *n* ≤ 5000). It is the number of cities in Berland. The second line contains *n* space-separated integers *a*_{1}, *a*_{2}, ..., *a*_{n}, where *a*_{i} represents the priority of the division, located in the city number *i*. All numbers *a*_{1}, *a*_{2}, ..., *a*_{n} are different (1 ≤ *a*_{i} ≤ 10^{9}). Then *n* - 1 lines contain the descriptions of the railway roads. Each description consists of three integers *v*_{j}, *u*_{j}, *c*_{j}, where *v*_{j}, *u*_{j} are number of cities connected by the *j*-th rail, and *c*_{j} stands for the maximum capacity of a train riding on this road (1 ≤ *v*_{j}, *u*_{j} ≤ *n*, *v*_{j} ≠ *u*_{j}, 1 ≤ *c*_{j} ≤ *n*).

Output

Print sequence *t*_{1}, *t*_{2}, ..., *t*_{n}, where *t*_{i} stands for the number of days it takes for the division of city *i* to arrive to the capital. Separate numbers with spaces.

Examples

Input

4

40 10 30 20

1 2 1

2 3 1

4 2 1

Output

0 1 3 2

Input

5

5 4 3 2 1

1 2 1

2 3 1

2 4 1

4 5 1

Output

0 1 4 2 3

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2019 21:44:59 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|