Farmer John 农场有 $N$ 座谷仓（$2\le N\le2\cdot10^5$），编号 $1\ldots N$，以及 $N-1$ 条各连接两谷仓的道路。任意谷仓可经道路到达其他谷仓。第 $j$ 座目前有 $h_j$ 捆干草（$1\le h_j\le10^9$）。

为使牛开心，FJ 想移动干草使每座谷仓数量相等。他可选择道路连接的一对谷仓，命令工人把不超过第一座当前干草数的任意正整数捆干草，从第一座搬到第二座。

求以最少命令完成任务的命令序列，保证存在。

输入格式

首行是 $N$。

次行是空格分隔的 $h_j$，$j=1\ldots N$。

最后 $N-1$ 行各有空格分隔的谷仓编号 $u_i,v_i$，表示连接两者的双向道路。

输出格式

先输出最少命令数，再输出等长命令序列，每行一个。

每命令为三个空格分隔的正整数：源谷仓、目标谷仓、从源搬到目标的干草捆数。

多解时输出任意一个。

样例

输入格式 1

4
2 1 4 5
1 2
2 3
2 4

输出格式 1

3
3 2 1
4 2 2
2 1 1

说明

本例 $12$ 捆草、$4$ 座谷仓，最终各 $3$ 捆。样例命令可表述为：

1. 从 $3$ 到 $2$ 搬 $1$ 捆。

2. 从 $4$ 到 $2$ 搬 $2$ 捆。

3. 从 $2$ 到 $1$ 搬 $1$ 捆。

子任务

• 测试 $2\ldots8$：$N\le5000$。

• 测试 $7\ldots10$：$v_i=u_i+1$。

• 测试 $11\ldots16$：无额外限制。

题目作者：Aryansh Shrivastava