Description

Farmer John’s farm has $N$ barns $(2 \le N \le 2 \times 10^5)$, labeled $1 \cdots N$. There are $N−1$ roads, each connecting two barns, and from any barn it is possible to reach any other barn via some roads. Currently, barn $j$ contains $h_j$ haybales $(1 \le h_j \le 10^9)$.

To keep his cows happy, Farmer John wants to move the hay so that every barn has the same number of haybales. He may choose any pair of barns connected by a single road and instruct his farmhands to move any positive integer number of haybales, up to the amount in the first barn, from the first barn to the second barn.

Find a sequence of commands that Farmer John can issue to complete this task using as few commands as possible. The input guarantees that such a sequence exists.

Input Format

The first line contains the integer $N$.

The second line contains space-separated integers $h_j$ for $j=1 \cdots N$.

Each of the last $N−1$ lines contains two space-separated barn indices $u_i, v_i$, indicating there is a bidirectional road between $u_i$ and $v_i$.

Output Format

Output the minimum number of commands, then output a sequence of that many commands, one per line.

Each command should be three space-separated positive integers: the source barn, the destination barn, and the number of haybales moved from the source to the destination.

If there are multiple solutions, output any of them.

4
2 1 4 5
1 2
2 3
2 4

3
3 2 1
4 2 2
2 1 1

Hint

Sample 1 Explanation

In this example, there are twelve haybales and four barns, which means each barn must end up with three haybales. The sequence in the sample output can be described in natural language as follows:

1. From barn $3$ to barn $2$, move $1$ haybale.
2. From barn $4$ to barn $2$, move $2$ haybales.
3. From barn $2$ to barn $1$, move $1$ haybale.

Testpoint Properties

• Testpoints $2-8$ satisfy $N \le 5000$.
• Testpoints $7-10$ satisfy $v_i=u_i+1$.
• Testpoints $11-16$ have no additional constraints.

Translated by ChatGPT 5