Marica ir ieķērusies Marko un ļoti vēlas ar viņu satikties. Tā kā Marica nedzīvo tajā pašā pilsētā kur Marko, viņa ir sākusi gatavoties garam ceļojumam.

Katras divas pilsētas valstī savieno vismaz viena šoseja, un katrai no šosejām ir zināms laiks, cik minūtes nepieciešamas, lai no vienas pilsētas nonāktu otrā.

Mirko pa ausu galam ir dzirdējis, ka viena no šosejām ir slēgta, bet viņš ir palaidis garām, kura tieši. No pilsētas, kurā dzīvo Marica, līdz pilsētai, kurā dzīvo Mirko, ir iespējams nokļūt neatkarīgi no tā, kura šoseja ir slēgta.

Marica pārvietosies tikai pa šosejām, kas nav slēgtas, un izvēlēsies ātrāko maršrutu. Tā kā Mirko ir ļoti nepacietīgs, viņš vēlas uzzināt, vēlākais pēc cik minūtēm Marica ieradīsies viņa pilsētā.

Uzrakstiet programmu, kas nosaka ilgāko laiku minūtēs, cik var aizņemt Maricas ceļojums!

Ievaddatu pirmajā rindā dotas divu naturālu skaitļu N (pilsētu skaits, 1 ≤N≤1000) un M(šoseju skaits, 1≤M≤N*(N-1)/2) vērtības, kas atdalītas ar tukšumsimbolu. Pilsētas ir numurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas. Mirko dzīvo pilsētā 1, bet Marica - pilsētā N.

Nākošajās M faila rindās katrā dots pa vienas divvirzienu šosejas aprakstam un katra satur trīs naturālu skaitļu A(1≤A≤N), B(1≤B≤N) un V(1≤V≤1000) vērtības, kas atdalītas ar tukšumsimboliem. A un B ir to pilsētu, kuras šī soseja savieno, numuri, bet V ir laiks minūtēs, kāds nepieciešams, lai aizbrauktu pa šo šoseju no vienas pilsētas līdz otrai.

Izvaddatu vienīgajā rindā jāizvada lielākais skaits minūtēs, cik var aizņemt Maricas ceļojums pa ātrāko iespējamo maršrutu.

Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā