Farmer John è troppo pigro per mantenere i sentieri dei suoi $N$ pascoli ($5\le N\le10{,}000$), numerati $1\ldots N$. Ognuno ospita una mucca. Vuole rimuovere il massimo dei $P$ sentieri ($N-1\le P\le100{,}000$) mantenendo la connessione. Scegli i $N-1$ da conservare.

Sentiero bidirezionale $j$ collega $S_j,E_j$ ($1\le S_j\le N;1\le E_j\le N;S_j\ne E_j$), tempo $L_j$ ($0\le L_j\le1{,}000$). Al massimo uno diretto per coppia.

Le mucche sono tristi per la riduzione dei trasporti. Visita ognuna almeno una volta al giorno per rallegrarla. Ogni visita a $i$, anche di passaggio, richiede parlare per $C_i$ ($1\le C_i\le1{,}000$).

Dormi ogni notte nello stesso pascolo scelto finché si riprendono. Parlerai con la sua mucca almeno al risveglio e la sera al ritorno per dormire.

Se FJ conserva i sentieri proposti e scegli il pascolo ottimo per dormire, trova il minimo tempo quotidiano per visitare ognuna almeno una volta.

Per le prime $10$ consegne riceverai risultati su parte dei dati reali.

Input

• Riga $1$: interi $N,P$ con uno spazio.

• Righe $2\ldots N+1$: riga $i+1$, intero $C_i$.

• Righe $N+2\ldots N+P+1$: riga $N+j+1$, interi $S_j,E_j,L_j$ con spazi.

Output

• Riga $1$: intero, tempo totale incluse due visite alla mucca del pascolo dove dormi.

Esempi

Input 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

Output 1

176

Spiegazione

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

Conserva questi sentieri:

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

Svegliati in $4$, visita $4,5,4,2,3,2,1,2,4$ e impiega $176$ prima di dormire.

Sottoproblemi

Punti: $300$

Autori del problema: David Benjamin e Jacob Steinhardt, 2008