402810: GYM100886 E Evacuation Plan

The main office of the Berland Bruteforce Corporation consists of n rooms, connected by n - 1 passages. There is exactly one way to travel between any pair of rooms using these passages (seeing this phrase, one who is familiar with the graph theory immediately recognizes an undirected tree). Let's assume that the rooms are numbered with consecutive integers from 1 to n. There are e_i employees working at room i. For each passage, its length (in meters) is known.

The recent earthquakes have convinced the board of BBC to create an evacuation plan for the employees. In a plan, there should be a single evacuation point, which may be located either at some room or at any place in a passage. In the latter case, a new room is created. This new room divides the passage of length L into two passages of lengths L₁ and L₂ (L₁ + L₂ = L).

Once the evacuation point is set, the evacuation happens as follows. At the time 0 (the beginning of evacuation), all employees simultaneously try to start moving towards the evacuation point. It takes exactly s seconds for a person to walk 1 meter. Passages have limited capacity c, which is the same for all passages: at most c persons can enter the passage at a time step. Let us clarify this a bit. Consider some passage. It is clear that people will move through it only in one of the two possible directions. At time 0, at most c persons can enter the passage. Then, nobody can enter the passage until time 1, when again at most c persons can enter the passage, an so on. There is no limit on the number of persons that can be in a room or in a passage at the same moment of time.

The BBC board is interested in such a plan that minimizes the time of the evacuation: the time when every person reaches the evacuation point. Help them to create it.

The first line contains three integers n, c and s (1 ≤ n ≤ 10⁵, 1 ≤ c ≤ 10⁴, 1 ≤ s ≤ 100): the number of rooms, the capacity of each passage and the time needed to walk 1 meter. The second line contains n integers e₁, e₂, ..., e_n (1 ≤ e_i ≤ 10⁶). Each of the next n - 1 lines contains three integers u, v and d (1 ≤ u, v ≤ n, 1 ≤ d ≤ 10⁴), meaning that there is a passage of length d meters between rooms u and v.

Print the optimal location of the evacuation point. If you are going to place the point in an existing room, print its number. Otherwise, print three numbers u, v and x, meaning that the evacuation point must be placed in the passage connecting rooms u and v at the distance of x meters from u. The number x must belong to the interval (0, l) where l is the length of the passage between u and v.

Your answer will be considered correct if the evacuation time in your plan has an absolute or relative error of at most 10^- 9 from an optimal one.

2 2 1
5 5
1 2 3

1 2 1.500000000000

2 2 1
5 10
1 2 3

1 2 2.500000000000

3 2 10
8 6 8
1 2 10
2 3 10

2

4 3 1
3 8 4 7
1 2 2
2 3 1
2 4 5

2 4 1.500000000000

Let's go through the evacuation in the fourth sample step-by-step.

• t = 0:
  • 3 persons enter the passage (1, 2) from room 1, they'll arrive at room 2 at t = 2.
  • 3 persons enter the passage (3, 2) from room 3, they'll arrive at room 2 at t = 1.
  • 3 persons enter the passage (4, 2) from room 4, they'll arrive at evacuation point at t = 3.5.
  • 3 persons enter the passage (2, 4) from room 2, they'll arrive at evacuation point at t = 1.5.
• t = 1:
  • 1 person enters the passage (3, 2) from room 3, she'll arrive at room 2 at t = 2.
  • 3 persons from room 4 arrive at room 2.
  • 3 persons enter the passage (4, 2) from room 4, they'll arrive at evacuation point at t = 4.5.
  • 3 persons enter the passage (2, 4) from room 2, they'll arrive at evacuation point at t = 2.5.
• t = 2:
  • 3 persons from room 1 and 1 person from room 3 arrive at room 2.
  • 1 person enters the passage (4, 2) from room 4, she'll arrive at evacuation point at t = 5.5.
  • 3 persons enter the passage (2, 4) from room 2, they'll arrive at evacuation point at t = 3.5.
• t = 3:
  • 3 persons enter the passage (2, 4) from room 2, they'll arrive at evacuation point at t = 4.5.
• t = 4:
  • 3 persons enter the passage (2, 4) from room 2, they'll arrive at evacuation point at t = 5.5.

Evacuation finishes in 5.5 seconds.