Zima [B]

Limit pamięci: 128 MB

W Bajtocji nastała zima. Bajtazar, kierowca pługu, nie dał się zaskoczyć i ruszył do odśnieżania ulic Bajtogrodu.

Sieć drogowa w Bajtogrodzie składa się z skrzyżowań połączonych dwukierunkowymi ulicami. Z każdego skrzyżowania do każdego innego da się dojechać bez zawracania dokładnie jedną trasą złożoną z jednej lub większej liczby ulic.

Śnieg pada nieustannie, dlatego ulice należy ciągle odśnieżać od nowa. Dla każdej ulicy Bajtazar wie, ile co najmniej razy powinien ją odśnieżyć w ciągu dnia (nie jest dla niego istotne, w których momentach dnia to uczyni). Bajtazar może rozpocząć odśnieżanie przy dowolnym skrzyżowaniu. Chciałby on tak zaplanować swą pracę, by łączna liczba przejechanych ulic była jak najmniejsza. Oczywiście wielokrotne przejechanie tej samej ulicy należy liczyć wiele razy.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą () oznaczającą liczbę skrzyżowań w Bajtogrodzie. W kolejnych wierszach opisane są poszczególne ulice. W każdym z tych wierszy znajdują się trzy liczby całkowite (, , ) oznaczające, że skrzyżowania oraz są połączone dwukierunkową ulicą, którą należy odśnieżyć co najmniej razy w ciągu dnia.

Wyjście

Na wyjście należy wypisać jeden wiersz zawierający minimalną liczbę ulic, którymi musi przejechać Bajtazar, by spełnić podane wymagania.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

8

Wyjaśnienie do przykładu: Najlepsza trasa Bajtazara przebiega ośmioma ulicami: .