Uolevin tädin perunakellari joutui röyhkeän varkauden kohteeksi. Tekijä Tiirikka-Timppa on pakomatkalla, ja poliisi haluaa saada hänet kiinni, ennen kuin hän pääsee satamaan ja sen jälkeen ulos maasta.

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 perunakellarista 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. Perunakellari on risteyksessä 1 ja satama on risteyksessä n.

Sitten syötteessä on m riviä, joista jokainen kuvaa yhden tien. Rivillä on kolme kokonaislukua a_i, b_i ja k_i: 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

• 1 \le n \le 100
• 1 \le m \le 200
• 1 \le a_i, b_i \le n
• 1 \le k_i \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