Farmer John の農場には $N$ 納屋（$2\le N\le2\cdot10^5$）、番号 $1\ldots N$ と、それぞれ 2 納屋を結ぶ $N-1$ 本の道があり、どこからでも他に行けます。納屋 $j$ に干し草 $h_j$ 束（$1\le h_j\le10^9$）があります。

牛を喜ばせるため草を移して全納屋を同じ束数にします。道で結ばれた 2 納屋を選び、最初の現在の束数以下の任意の正整数束を最初から 2 番目へ運ぶよう作業員に命令できます。

最少命令で完了する命令列を求めます。存在は保証されます。

入力

最初の行は $N$。

次は空白区切りの $h_j$（$j=1\ldots N$）。

最後の $N-1$ 行は空白区切りの納屋番号 $u_i,v_i$、その間の双方向の道です。

出力

最少命令数と、その長さの命令列を 1 行 1 命令で出します。

各命令は空白区切りの正整数 3 個：出発納屋、行き先、運ぶ束数です。

複数解なら任意の解を出します。

入出力例

入力 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