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.