Struktury Danych

Ze struktur danych dostaliśmy wyobraźcie sobie do napisania program! Kto by pomyślał?

Oto treść:

Motel
Dost˛epna pami˛e´ c: 64MB.
Profesor Makary wybiera si˛e na zimowy urlop na narty. Poniewa˙ z droga z domu profesora do górskiego kurortu jest daleka,
profesor liczy si˛e z konieczno´ sci ˛a podzielenia jej na dwa dzienne etapy, z noclegiem w przydro˙ znym motelu. Podró˙ ze go m˛ecz ˛a,
wi˛ec tras˛e i miejsce na nocleg chce wybra´ c tak, ˙ zeby oba fragmenty drogi nie były zbyt długie. Dokładniej, chciałby, aby dłu˙ zszy
z dwóch dziennych etapów był mo˙ zliwie najkrótszy.
Pomó˙ z profesorowi zaplanowa´ c tras˛e dojazdu, pisz ˛ac program, który obliczy najmniejsz ˛a mo˙ zliw ˛a długo´ s´ c dłu˙ zszego etapu.
UWAGA: Mo˙ ze si˛e zdarzy´ c, ˙ ze w optymalnym rozwi ˛azaniu który´ s z etapów ma długo´ s´ c 0 (czyli w rzeczywisto´ sci cała trasa
zostanie przebyta w jednym etapie).
Wej´ scie
W pierwszym wierszu znajduj ˛a si˛e dwie liczby całkowite n i m (2 ? n ? 50000, 1 ? m ? 1000000). Pierwsza z nich oznacza
liczb˛e punktów stanowi ˛acych potencjalne miejsca postoju, ponumerowanych od 0 do n?1 (punkt numer 0 to dom profesora,
punkt n?1 to kurort, a pozostałe to motele). Druga to liczba odcinków dróg ł ˛acz ˛acych punkty. Ka˙ zdy z kolejnych m wierszy
zawiera trzy liczby całkowite a, b, c, gdzie 0?a,b<n, a 6=b, 0?c?10000. Liczby a i b oznaczaj ˛a punkty na drogach, za´ s c to
długo´ s´ c odcinka drogi prowadz ˛acego bezpo´ srednio od a do b. (UWAGA: długo´ sci odcinków dróg od a do b i od b do a nie musz ˛a
by´ c równe; w szczególno´ sci który´ s z nich mo˙ ze wcale nie istnie´ c). Liczby w ka˙ zdym wierszu s ˛a pooddzielane pojedynczymi
spacjami.
Wyj´ scie
W jedynym wierszu standardowego wyj´ scia nale˙ zy wypisa´ c najmniejsz ˛a mo˙ zliw ˛a długo´ s´ c dłu˙ zszego z dwóch etapów drogi z
domu profesora do kurortu.
Przykład
Dla danych wej´ sciowych:
4 5
0 1 1
0 2 4
1 2 2
1 3 4
2 3 3
poprawnym wynikiem jest:
3
Wyja´ snienie do przykładu. Optymalna trasa to: 0?1?2 (I etap); 2?3 (II etap)

A oto rozwiązanie:
Jakoś działa, z większy naciskiem na JAKOŚ niż na DZIAŁA
Zadanie