Die Zwerge haben gerade ihr neues unterirdisches Dorf gebaut. Jetzt ist es an der Zeit, das Eisenbahnnetz zu planen, das darin betrieben werden soll.

Das Dorf besteht aus $N$ Kreuzungen und $N - 1$ Tunneln, die diese verbinden. Die Tunnel wurden so gebaut, dass man von jeder Kreuzung aus jede andere erreichen kann. An jeder Kreuzung, die eine Sackgasse ist (was bedeutet, dass sie nur durch einen einzigen Tunnel verbunden ist), befindet sich ein Bahnhof.

Deine Aufgabe ist es, die Routen für die Züge im Dorf festzulegen. Um die Anforderungen der Zwerge zu erfüllen, müssen alle Bahnhöfe paarweise zugeordnet werden (glücklicherweise gibt es eine gerade Anzahl davon), und zwischen jedem Paar wird ein Zug auf dem kürzestmöglichen Weg verkehren. Die Tunnel haben jedoch ihre Grenzen. Obwohl jeder Tunnel die gleiche Länge hat (gleich $1$), erlaubt ihre Breite nur einer begrenzten Anzahl von Routen die Durchfahrt.

Die Zwerge möchten, dass die Gesamtlänge der Zugrouten so groß wie möglich ist. Kannst du berechnen, wie groß die maximale Länge sein kann?

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl $N$, die Anzahl der Kreuzungen im Dorf.

Jede der nächsten $N - 1$ Zeilen enthält drei ganze Zahlen $a_i$, $b_i$, $c_i$, die einen Tunnel zwischen den Kreuzungen $a_i$ und $b_i$ darstellen. Der Wert $c_i$ ist eine Obergrenze für die Anzahl der Routen, die durch diesen Tunnel führen dürfen.

Ausgabe

Gib in der ersten und einzigen Zeile eine einzige ganze Zahl aus, die die maximale Gesamtlänge der Wege zwischen den gewählten Bahnhofspaaren darstellt.

Wenn es keine Möglichkeit gibt, die Bahnhöfe unter Einhaltung der Bedingungen paarweise zuzuordnen, gib $-1$ aus.

Einschränkungen

$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, alle Kreuzungen sind miteinander verbunden, und die Anzahl der Bahnhöfe (d. h. Sackgassen) ist gerade.

Beispiele

Eingabe 1

10
1 2 2
2 3 1
3 4 3
5 1 1
6 1 2
7 2 3
8 3 2
9 3 1
10 4 7

Ausgabe 1

10

Hinweis

Im ersten Beispiel ergibt das Verbinden der Bahnhöfe an den Kreuzungen $5\text{--}9$, $6\text{--}7$ und $8\text{--}10$ eine Gesamtlänge der Zugrouten von $4 + 3 + 3 = 10$.

Eingabe 2

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

Ausgabe 2

-1