Zawody
Limit pamięci: 16 MB
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ę).
Zadanie
Pomóż Bajtale!
Napisz program, który:
-
wczyta ze standardowego wejścia opis jaskini oraz
czasy potrzebne do przejścia poszczególnych korytarzy,
-
obliczy trasę zgodną z zasadami zawodów, dla której
suma czasów przejść korytarzy składających się na trasę
jest najmniejsza,
-
wypisze na standardowe wyjście czas potrzebny do przejścia
wyznaczonej trasy.
Wejście
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.
Wyjście
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.
Przykład
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.