La granja de Farmer John tiene $N$ graneros ($2\le N\le2\cdot10^5$), numerados $1\ldots N$, y $N-1$ caminos que conectan parejas. Se puede ir de cualquiera a cualquier otro. El $j$ tiene $h_j$ pacas ($1\le h_j\le10^9$).

Para contentar a las vacas, FJ mueve heno e iguala las cantidades. Elige dos graneros unidos y ordena mover del primero al segundo cualquier entero positivo de pacas, no mayor que la cantidad actual del primero.

Encuentra una secuencia con el mínimo de órdenes. Se garantiza su existencia.

Entrada

Primera línea: $N$.

Segunda: $h_j$ separados por espacios, $j=1\ldots N$.

Últimas $N-1$ líneas: números $u_i,v_i$ separados por un espacio, camino bidireccional entre ellos.

Salida

Imprime el mínimo de órdenes y una secuencia de esa longitud, una por línea.

Cada orden: tres enteros positivos separados por espacios, origen, destino y cantidad de pacas trasladadas.

Si hay varias soluciones, imprime cualquiera.

Ejemplos

Entrada 1

4
2 1 4 5
1 2
2 3
2 4

Salida 1

3
3 2 1
4 2 2
2 1 1

Nota

$12$ pacas y $4$ graneros, finalmente $3$ cada uno. Las órdenes significan:

1. De $3$ a $2$, mover $1$ paca.

2. De $4$ a $2$, mover $2$ pacas.

3. De $2$ a $1$, mover $1$ paca.

Subtareas

• Tests $2\ldots8$: $N\le5000$.

• Tests $7\ldots10$: $v_i=u_i+1$.

• Tests $11\ldots16$: sin restricciones adicionales.

Autor del problema: Aryansh Shrivastava