Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Pakomatka

Pakomatka


View task | Model solution | Statistics


Pakomatka

Time limit:1.00 s
Memory limit:128 MB

Tiirikka-Timppa on ryöstänyt pankin ja pakomatkalla kohti satamaa. Poliisi aikoo saada Timpan satimeen sulkemalla joukon kaupungin teitä. Tiedossasi on jokaisesta tiestä kustannus, jonka sen sulkeminen aiheuttaa.

Tehtäväsi on valita suljettavat tiet niin, että kaikki reitit pankista satamaan on estetty ja kokonaiskustannus on mahdollisimman pieni.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: risteysten määrä ja teiden määrä. Risteykset on numeroitu kokonaisluvuin $1,2,\ldots,n$. Pankki on risteyksessä $1$ ja satama on risteyksessä $n$.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa yhden tien. Rivillä on kolme kokonaislukua $a$, $b$ ja $c$: mistä risteyksestä tie alkaa, mihin risteykseen se päättyy ja mikä on sen sulkemisen kustannus. Kaikki tiet ovat yksisuuntaisia, ja kahden risteyksen välillä on enintään yksi tie.

Tuloste

Ohjelmasi tulee tulostaa ensimmäiselle riville kokonaiskustannus, jonka teiden sulkeminen aiheuttaa.

Seuraavalla rivillä tulee olla suljettavien teiden määrä, ja lopuksi jokainen suljettava tie omalla rivillään.

Jos ratkaisuja on useita, voit tulostaa niistä minkä tahansa.

Rajat
Esimerkki

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


Tuloste:
3
2
2 4
3 4