Bessie plant das jährliche große Treffen für Kühe im ganzen Land und möchte den bequemsten Ort.

Jede wohnt in einer von $N$ ($1 \le N \le 100,000$) Scheunen, Nummern $1..N$, durch $N-1$ Straßen verbunden und alle erreichbar. Straße $i$ verbindet $A_{i}$ und $B_{i}$ ($1 \le A_i \le N; 1 \le B_i \le N$), Länge $L_{i}$ ($1 \le L_{i} \le 1,000$). Jeder der $N$ Orte möglich; in Scheune $i$ wohnen $C_{i}$ ($0 \le C_{i} \le 1,000$) Kühe.

Maximal bequem heißt minimal unbequem. Für $X$ ist das die Summe der Strecken aller Kühe nach $X$. Ist von $i$ nach $X$ Abstand 20, reisen sie $C_{i}*20$. Finde den besten Ort.

Fünf Scheunen mit verschiedenen Kuhzahlen in Klammern und Straßenlängen. 3 und 4 ohne Kühe.

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

Jeder Ort möglich; Tabelle der Unbequemlichkeit, B1–B5 Scheunen, letzte Spalte Summe.

Bei Treffen in 1 je Scheune:

• Scheune 1: 0, keine Reise!
• Scheune 2: 3, Strecke $2+1=3$ mal 1 Kuh ergibt 3.
• Scheune 3: 0, keine Kühe!
• Scheune 4: 0, keine Kühe!
• Scheune 5: 14, Strecke $3+3+1=7$ mal 2 Kühe ergibt 14.

Insgesamt 17 Unbequemlichkeit.

Bestes Ergebnis 15 bei Treffen in 3, 4 oder 5.

Eingabe

• Zeile 1: ganze Zahl $N$.
• Zeilen $2..N+1$: Zeile $i+1$, ganze Zahl $C_{i}$.
• Zeilen $N+2..2N$: Zeile $i+N+1$, ganze Zahlen $A_{i}$, $B_{i}$, $L_{i}$.

Ausgabe

• Zeile 1: kleinste mögliche Unbequemlichkeit.

Beispiele

Eingabe 1

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

Ausgabe 1

15

Autor: Jeffrey Wang, aus einem Wettbewerb, 2010