Farmer John est trop paresseux pour entretenir les chemins vers ses $N$ pâturages ($5\le N\le10{,}000$), numérotés $1\ldots N$. Chacun abrite une vache. Il veut supprimer un maximum des $P$ chemins ($N-1\le P\le100{,}000$), en gardant la connexité. Déterminez lesquels des $N-1$ conserver.

Le chemin bidirectionnel $j$ relie $S_j,E_j$ ($1\le S_j\le N;1\le E_j\le N;S_j\ne E_j$), en temps $L_j$ ($0\le L_j\le1{,}000$). Au plus un chemin direct par paire.

Les vaches sont tristes de perdre des transports. Visitez chacune au moins une fois par jour. À chaque visite de $i$, même un passage, parlez-lui pendant $C_i$ ($1\le C_i\le1{,}000$).

Dormez chaque nuit au même pâturage choisi jusqu’à leur rétablissement. Vous parlerez à sa vache au moins au réveil et le soir au retour pour dormir.

Si FJ conserve vos chemins et le lieu de sommeil est optimal, trouvez le temps quotidien minimal pour visiter chacune au moins une fois.

Pour vos $10$ premières soumissions, les résultats sur une partie des véritables tests seront fournis.

Entrée

• Ligne $1$ : entiers $N,P$ séparés par un espace.

• Lignes $2\ldots N+1$ : ligne $i+1$, entier $C_i$.

• Lignes $N+2\ldots N+P+1$ : ligne $N+j+1$, entiers $S_j,E_j,L_j$ séparés par des espaces.

Sortie

• Ligne $1$ : entier, temps total des visites, incluant deux visites à la vache du pâturage de sommeil.

Exemples

Entrée 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

Sortie 1

176

Remarque

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

Conservez ces chemins :

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

Réveillez-vous en $4$ et visitez $4,5,4,2,3,2,1,2,4$, pour $176$ de temps avant le sommeil.

Sous-tâches

Points : $300$

Auteurs du problème : David Benjamin et Jacob Steinhardt, 2008