Tramwaje

Limit pamięci: 128 MB

Bajtazar został nowym ekspertem ds. komunikacji tramwajowej w Bajtocji. Bardzo chciałby przysłużyć się mieszkańcom miasta i pomyślał, że najlepszym sposobem będzie zreformowanie planu tras tramwajów. Oczywiście, trzeba to zrobić mądrze!

Sieć tramwajowa w Bajtocji składa się z skrzyżowań i odcinków torów; z każdego skrzyżowania można dojechać torami do dowolnego innego. Przy każdym skrzyżowaniu, do którego dochodzi tylko jeden odcinek torów, znajduje się pętla tramwajowa. Bajtazar ma dwa wymagania odnośnie planu tras. Po pierwsze, każda trasa musi zaczynać się na pewnej pętli i kończyć się na innej pętli. Po drugie, przez każdy odcinek torów musi przebiegać pewna trasa.

Bajtazar zastanawia się jaka jest minimalna sumaryczna długość tras dla pewnego poprawnego planu.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę skrzyżowań w sieci tramwajowej. Skrzyżowania są ponumerowane liczbami od 1 do . W -tym z kolejnych wierszy znajdują się po trzy liczby całkowite , , (, , ) oznaczające numery skrzyżowań, które łączy -ty odcinek torów, oraz długość tego odcinka.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć minimalna sumaryczna długość tras tramwajowych, którą da się uzyskać dla jakiegoś poprawnego planu.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

11

Autor zadania: Tomasz Idziaszek.