Krowy nie znoszą gimnastyki (ćwiczeń), ale trochę lubią trucht. Zbadały pastwisko i spisały wszystkie możliwe ścieżki. Są „skierowane”: można iść tylko w jednym kierunku. Czasem dwie różne ścieżki łączą parę punktów w przeciwnych kierunkach.

Znajdź najkrótszą „trasę okrężną” do truchtu. Zaczyna się i kończy w tym samym miejscu. Długość jest sumą długości ścieżek przebytych podczas okrążenia.

Ścieżki łączą dwa punkty, nazwane dodatnimi liczbami całkowitymi kolejno od 1. Odległości to dodatnie liczby całkowite.

Każde podane pastwisko ma przynajmniej jedną trasę okrężną.

Wejście

• Wiersz $1$: $N$ ($1 \le N \le 2000$), liczba ścieżek skierowanych; najwyżej 400 różnych punktów.
• Wiersze $2..N+1$: początek, koniec i odległość (najwyżej 1000) jednej ścieżki.

Wyjście

Jeden wiersz z całkowitą odległością najkrótszego możliwego obwodu.

Przykład

Wejście 1

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

Wyjście 1

12

Autorzy zadania: Hal Burch i Russ Cox