Problem description

Państwo Bajtocji składa się z N miast połączonych między sobą dokładnie N dwukierunkowymi drogami. Ponadto z każdego miasta można dojechać do dowolnego innego.

Burmistrz Bajtocji zainteresował się infrastrukturą drogową swojego kraju. Zaczął się zastanawiać jaki jest stopień rozległości sieci drogowej. Stopień rozległości zdefiniował jako sumę długości najkrótszych ścieżek między każdą parą miast. Jako jego najlepszy doradca, pomóż mu i napisz program, który policzy stopień rozległości Bajtocji.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N oznaczająca liczbę miast Bajtocji. W następnych N wierszach znajduje się opis dróg Bajtocji. Każdy z nich składa się z trzech liczb u, v, w oznaczających, że miasta o numerach u oraz v połączone są drogą o długości w. Możesz założyć, że każda para miast występuje na wejściu co najwyżej raz.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą oznaczającą stopień rozległości Bajtocji.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ u, v ≤ N, 1 ≤ w ≤ 1 000 000.

W testach wartych 20% punktacji zachodzi warunek N ≤ 2 000.

Przykład

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

50