Kühe hassen Gymnastik (Übungen), mögen aber etwas Joggen. Sie haben die Weide erkundet und alle möglichen Wege aufgelistet. Die Wege sind „gerichtet“: nur in einer Richtung begehbar. Manchmal verbinden zwei verschiedene Wege ein Punktpaar in entgegengesetzten Richtungen.

Finden Sie die kürzeste „Rundroute“ zum Joggen. Sie beginnt und endet am selben Ort. Ihre Länge ist die Summe der Längen der bei einer Runde benutzten Wege.

Wege verbinden zwei Punkte. Diese heißen positive ganze Zahlen und sind ab 1 fortlaufend nummeriert. Entfernungen sind positive ganze Zahlen.

Jede gegebene Weide enthält garantiert mindestens eine Rundroute.

Eingabe

• Zeile $1$: $N$ ($1 \le N \le 2000$), Zahl gerichteter Wege; höchstens 400 verschiedene Punkte.
• Zeilen $2..N+1$: Anfang, Ende und Entfernung (höchstens 1000) eines Weges.

Ausgabe

Eine Zeile mit der ganzzahligen Entfernung des kürzesten möglichen Rundwegs.

Beispiele

Eingabe 1

4
3 1 5
1 2 4
2 3 3
1 3 44

Ausgabe 1

12

Aufgabenautoren: Hal Burch und Russ Cox