Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Tutkimus

Tutkimus


View task | Model solution | Statistics


Tutkimus

Time limit:1.00 s
Memory limit:128 MB

Uolevi aikoo jälleen kerran matkustaa Syrjälästä Lehmälään mahdollisimman halvalla. Sinulle on annettu tiedot lennoista kaupunkien välillä ja tehtäväsi on selvittää seuraavat asiat:
Huomaa, että lentojen muodostamassa verkossa voi olla syklejä.

Syöte

Syötteessä on ensin kaksi kokonaislukua $n$ ja $m$: kaupunkien määrä ja lentojen määrä. Kaupungit on numeroitu $1,2,\ldots,n$. Syrjälän numero on 1, ja Lehmälän numero on $n$.

Sitten syötteessä on $m$ riviä, jotka kuvaavat lennot. Jokaisella rivillä on kolme kokonaislukua $a$, $b$ ja $c$: kaupungista $a$ on lento kaupunkiin $b$ hintaan $c$. Kaikki lennot ovat yksisuuntaisia.

Tuloste

Tulosta neljä kokonaislukua tehtävänannon mukaisesti.

Rajat
Esimerkki

Syöte:
4 5
1 4 5
1 2 4
2 4 5
1 3 2
3 4 3


Tuloste:
5 2 1 2