Nosaukums
Maricas ceļojums (marica)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

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 raksturojums

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 raksturojums

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.


Piezīmes

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


Paraugdati

Stdin
6 7
1 2 1
2 3 4
3 4 4
4 6 4
1 5 5
2 5 2
5 6 5
Stdout
13

Stdin
5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
Stdout
27

Stdin
5 6
1 2 4
1 3 3
2 3 1
2 4 4
2 5 7
4 5 1
Stdout
11

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.