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.
U stóp Bajtogóry znajduje się wejście do jaskini. Jaskinia to system komnat połączonych korytarzami. Wejście do jaskini prowadzi bezpośrednio do komnaty nazywanej wejściową. Korytarze nie przecinają się (spotykają się jedynie w komnatach). Dwie komnaty mogą być albo połączone jednym korytarzem, albo mogą nie być połączone wcale (być może można jednak wtedy przejść z jednej do drugiej przechodząc po drodze przez inne komnaty). Korytarz łączy zawsze dwie różne komnaty.
Postanowiono zorganizować zawody o puchar króla Bajtocji. Celem każdego z zawodników jest przebycie dowolnie wybranej trasy w jaskini i wyjście na zewnątrz w jak najkrótszym czasie. Trasa musi przechodzić przez co najmniej jedną komnatę inną niż wejściowa. Obowiązują tylko dwie zasady: podczas wędrówki po jaskini, każdą komnatę można odwiedzić co najwyżej raz (z wyjątkiem komnaty wejściowej), podobnie tylko raz można przejść każdym z korytarzy.
Do zawodów przygotowuje się słynny grotołaz Bajtała. Bajtała długo trenował w jaskini i dokładnie poznał sieć korytarzy. Dla każdego z korytarzy wyznaczył czasy potrzebne do jego przejścia w każdą stronę. Czas potrzebny do poruszania się po komnatach można zaniedbać. Bajtała chciałby teraz wyznaczyć taką trasę spełniającą wymogi zawodów, którą można przebyć w jak najkrótszym czasie (czas potrzebny do przebycia trasy jest sumą czasów potrzebnych do przejścia korytarzy składających się na trasę).
Pomóż Bajtale! Napisz program, który:
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę komnat w jaskini, oraz liczbę łączących je korytarzy, , . Komnaty są ponumerowane od do . Komnata wejściowa ma numer . W kolejnych wierszach opisane są poszczególne korytarze. W każdym z tych wierszy znajduje się czwórka liczb naturalnych oddzielonych pojedynczymi odstępami. Czwórka oznacza, że jaskinie i są połączone korytarzem, czas przejścia z jaskini do wynosi , a z do wynosi , , , . Możesz założyć, że zawsze istnieje przynajmniej jedna trasa spełniająca wymogi zawodów.
Twój program powinien wypisać w pierwszym i jedynym wierszu wyjścia jedną liczbę całkowitą - minimalny czas potrzebny do przebycia trasy spełniającej warunki zawodów.
Dla danych wejściowych:
3 3 1 2 4 3 2 3 4 2 1 3 1 1
poprawną odpowiedzią jest:
6
Autor zadania: Łukasz Kowalik.