Barn Tree

문제

Farmer John's farm has $NN$ barns ($2\le N\le 2\cdot {10}^{5}2\; \backslash leq\; N\; \backslash leq\; 2\backslash cdot\; 10^5$) numbered $1\dots N1\; \backslash dots\; N$. There are $N-1N-1$ roads, where each road connects two barns and it is possible to get from any barn to any other barn via some sequence of roads. Currently, the $jj$th barn has $h_{j}h\_j$ hay bales ($1\le h_j\le {10}^{9}1\backslash le\; h\_j\backslash le\; 10^9$).

To please his cows, Farmer John would like to move the hay such that each barn has an equal number of bales. He can select any pair of barns connected by a road and order his farmhands to move any positive integer number of bales less than or equal to the number of bales currently at the first barn from the first barn to the second.

Please determine a sequence of orders Farmer John can issue to complete the task in the minimum possible number of orders. It is guaranteed that a sequence of orders exists.

입력

The first line of input contains the value of $N\mathrm{.}N.$

The second line of input contains the space-separated values of $h_{j}h\_j$ for $j=1\dots Nj\; =\; 1\; \backslash dots\; N$.

The final $N-1N-1$ lines of input each contain two space-separated barn numbers $u_i{v}_{i}u\_i\; \backslash \; v\_i$, indicating that there is a bidirectional road connecting $u_{i}u\_i$ and $v_{i}v\_i$.

출력

Output the minimum possible number of orders, followed a sequence of orders of that length, one per line.

Each order should be formatted as three space-separated positive integers: the source barn, the destination barn, and the third describes the number of hay bales to move from the source to the destination.

If there are multiple solutions, output any.

힌트

In this example, there are a total of twelve hay bales and four barns, meaning each barn must have three hay bales at the end. The sequence of orders in the sample output can be verbally translated as below:

1. From barn $33$ to barn $22$, move $11$ bale.
2. From barn $44$ to barn $22$, move $22$ bales.
3. From barn $22$ to barn $11$, move $11$ bale.

4
2 1 4 5
1 2
2 3
2 4

3
3 2 1
4 2 2
2 1 1