Fair Distribution

A farmers' guild produced grain and delivered it to a large food company. The company paid each of the N farmers the same amount X. Since the farmers did not all contribute the same amount of work, they want to redistribute the money more fairly.

Each farmer lives in a different village. The villages are connected by roads, and between any two villages there is exactly one path. In one transaction, a farmer drives a tractor to a directly neighboring village and gives any amount of money to the farmer living there.

For each farmer, the amount they deserve is known. Your program must determine both of the following:

1. The minimum number of transactions needed so that every farmer has at least the amount they deserve.
2. A list of transactions, in an order that achieves that minimum.

The order matters. A farmer may not give more money than they currently have.

The food company may have paid more money in total than the farmers require. In that case, the farmers do not care where the extra money remains, as long as every farmer has at least the amount they deserve.

The first line contains the number of farmers N. (1 <= N <= 2000)

The second line contains the amount X initially paid to each farmer. (0 <= X <= 10000)

The third line contains N integers. The i-th integer is the amount farmer i deserves. The sum of these N integers is at most N * X.

The next N - 1 lines describe the roads. Each line contains two village numbers A and B connected by a road. Village numbers are between 1 and N, and roads are bidirectional.

On the first line, output the minimum required number of transactions K.

On each of the next K lines, output one transaction as three integers A, B, and C. This means that the farmer from village A goes to village B and gives C units of money to the farmer there. Villages A and B must be directly connected by a road.

There may be several optimal transaction lists or valid orders. Output any one of them.