Bessie prépare le grand rassemblement annuel des vaches du pays et veut le lieu le plus commode.

Chaque vache vit dans l'une des $N$ ($1 \le N \le 100,000$) granges numérotées $1..N$, reliées par $N-1$ routes permettant de rejoindre toute autre. Route $i$ entre $A_{i}$ et $B_{i}$ ($1 \le A_i \le N; 1 \le B_i \le N$), longueur $L_{i}$ ($1 \le L_{i} \le 1,000$). Toute grange parmi $N$ peut accueillir ; la grange $i$ contient $C_{i}$ ($0 \le C_{i} \le 1,000$) vaches.

Maximiser le confort revient à minimiser l'incommodité : en $X$, somme des distances de toutes les vaches vers $X$. Si de $i$ à $X$ la distance est 20, le trajet total est $C_{i}*20$. Choisissez le meilleur lieu.

Cinq granges avec effectifs variés entre crochets et routes de longueurs variées. Les granges 3 et 4 sont vides.

      1     3     4     5
      @--1--@--3--@--3--@[2]
     [1]    |
            2
            |
            @[1]
            2

Tout lieu convient ; tableau des incommodités, B1–B5 sont les granges et dernière colonne la somme.

Si le rassemblement est en 1, incommodité par grange :

• Grange 1 : 0, aucun trajet !
• Grange 2 : 3, distance $2+1=3$ multipliée par 1 vache, soit 3.
• Grange 3 : 0, pas de vaches !
• Grange 4 : 0, pas de vaches !
• Grange 5 : 14, distance $3+3+1=7$ multipliée par 2 vaches, soit 14.

Incommodité totale 17.

La meilleure vaut 15, atteinte en 3, 4 ou 5.

Entrée

• Ligne 1 : entier $N$.
• Lignes $2..N+1$ : ligne $i+1$, un entier $C_{i}$.
• Lignes $N+2..2N$ : ligne $i+N+1$, trois entiers $A_{i}$, $B_{i}$, $L_{i}$.

Sortie

• Ligne 1 : incommodité minimale possible.

Exemples

Entrée 1

5
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3

Sortie 1

15

Auteur : Jeffrey Wang, issu d’un concours, 2010