W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
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.
Na wyjście należy wypisać jeden wiersz zawierający minimalną liczbę ulic, którymi musi przejechać Bajtazar, by spełnić podane wymagania.
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: .