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