Hay Redistribution on the Barn Network

Farmer John owns a farm consisting of \(N\) barns, numbered from \(1\) to \(N\) (where \(2 \le N \le 2 \times 10^5\)). There are \(N-1\) roads, each connecting two barns so that any barn can be reached from any other barn via a sequence of roads. Currently, the \(j^{th}\) barn contains \(h_j\) hay bales (with \(1 \le h_j \le 10^9\)).

Farmer John wants to redistribute the hay bales so that every barn ends up with the same number of hay bales. In one command, he can choose any pair of barns connected directly by a road, and instruct his workers to move any positive integer number of hay bales (not exceeding the number available in the source barn) from the first barn to the second barn.

Your task is to produce a sequence of commands achieving the redistribution with as few commands as possible. It is guaranteed that a valid sequence of commands exists.

Note: Let \(T\) be the total number of hay bales and \(k = T/N\) be the target number of hay bales per barn (it is guaranteed that \(T\) is divisible by \(N\)). One effective strategy is to root the tree (e.g. at barn 1) and perform a DFS. For each barn, compute the difference \(d = h_i - k\) and propagate this difference along the connecting roads. If a barn has a surplus (\(d>0\)), then move \(d\) hay bales from that barn to its parent; if it has a deficit (\(d<0\)), move \(-d\) hay bales from the parent to that barn. This creates exactly \(N-1\n commands, which is optimal under the given constraints.

inputFormat

The input begins with a single integer \(N\), the number of barns.

The second line contains \(N\) space-separated integers: \(h_1, h_2, \ldots, h_N\) representing the number of hay bales in each barn.

Each of the next \(N-1\) lines contains two integers \(u\) and \(v\) indicating a road between barns \(u\) and \(v\).

outputFormat

First, output an integer \(K\) representing the number of commands executed.

Then output \(K\) lines, each line containing three integers \(u\), \(v\), and \(x\). This means that \(x\) hay bales are moved from barn \(u\) to barn \(v\) (\(u\) and \(v\) are directly connected by a road).

sample

2
2 4
1 2

1
2 1 1