Polish version    English version  
  XVIII OI 2010/2011


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
Terminarz
Zadania
II Etap
Przepisy
Wyniki I etapu
Wyniki II etapu
Dla zawodników
Przydatne zasoby
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
XI Olimpiada Informatyczna 2003/2004

Zadanie: zaw

Zawody

Zawody I stopnia  
Plik źródłowy: zaw.xxx (xxx=pas,c,cpp)
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 n i m oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę komnat w jaskini, oraz liczbę łączących je korytarzy, 3 <= n <= 5000, 3 <= m <= 10000. Komnaty są ponumerowane od 1 do n. Komnata wejściowa ma numer 1. W kolejnych m wierszach opisane są poszczególne korytarze. W każdym z tych wierszy znajduje się czwórka liczb naturalnych oddzielonych pojedynczymi odstępami. Czwórka a, b, c, d oznacza, że jaskinie a i b są połączone korytarzem, czas przejścia z jaskini a do b wynosi c, a z b do a wynosi d, 1 <= a,b <= n, a <> b, 1 <= c,d <= 10000. 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

poprawnym wynikiem jest:

6



Wersja do druku