Farmer John es tan perezoso que no quiere mantener los caminos a sus $N$ pastos ($5\le N\le10{,}000$), numerados $1\ldots N$. Cada uno alberga una vaca. Quiere eliminar tantos de los $P$ caminos ($N-1\le P\le100{,}000$) como sea posible manteniendo la conexión. Elige los $N-1$ que conservar.

El camino bidireccional $j$ une $S_j,E_j$ ($1\le S_j\le N;1\le E_j\le N;S_j\ne E_j$), tiempo $L_j$ ($0\le L_j\le1{,}000$). Como máximo uno directo por pareja.

Las vacas están tristes por menos transporte. Visita cada una al menos una vez al día. Cada visita a $i$, incluso de paso, exige hablar durante $C_i$ ($1\le C_i\le1{,}000$).

Duerme cada noche en el mismo pasto elegido hasta que se recuperen. Hablarás con esa vaca al menos al despertar y por la tarde al volver a dormir.

Si FJ conserva tus caminos y eliges el pasto óptimo para dormir, halla el mínimo tiempo diario para visitar cada vaca al menos una vez.

En tus primeras $10$ entregas recibirás resultados sobre parte de los datos reales.

Entrada

• Línea $1$: enteros $N,P$ separados por un espacio.

• Líneas $2\ldots N+1$: línea $i+1$, entero $C_i$.

• Líneas $N+2\ldots N+P+1$: línea $N+j+1$, enteros $S_j,E_j,L_j$ separados por espacios.

Salida

• Línea $1$: entero, tiempo total incluyendo dos visitas a la vaca del pasto de descanso.

Ejemplos

Entrada 1

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

Salida 1

176

Nota

              +-(15)-+
             /        \
            /          \
     1-(5)-2-(5)-3-(6)--5
            \   /(17)  /
         (12)\ /      /(12)
              4------+

Conserva estos caminos:

     1-(5)-2-(5)-3      5
            \          /
         (12)\        /(12)
             *4------+

Despierta en $4$, visita $4,5,4,2,3,2,1,2,4$ y tarda $176$ antes de dormir.

Subtareas

Puntos: $300$

Autores del problema: David Benjamin y Jacob Steinhardt, 2008