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

• 2 \le n \le 100
• 1 \le m \le 1000
• 1 \le a, b \le n
• 1 \le c \le 10^9

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