Uolevilla on verkko jonka jokaisessa kaaressa on luku. Uolevi tekee verkkoon operaatiota. Yhdessä operaatiossa Uolevi poistaa verkosta kaksi kaarta joilla on yhteinen solmu. Uolevi saa operaatiossa pisteitä kaarien lukujen verran. Tehtäväsi on selvittää mikä on suurin määrä pisteitä minkä Uolevi voi saada, ja rakentaa joku optimaalinen tapa tehdä operaatiota.

Syöte

Syötteen ensimmäisellä rivillä on kaksi lukua, $n$ ja $m$, verkon solmujen ja kaarien määrät. Seuraavat $m$ riviä kuvaavat kaaret. Jokaisella rivillä on kolme lukua $u$, $v$ ja $c$, jotka tarkoittavat että kaari on solmujen $u$ ja $v$ välillä ja siinä on luku $c$.

Tuloste

Tulosta ensimmäiselle riville optimaalinen pistemäärä. Sen jälkeen tulosta luku $k$, operaatioiden määrä. Sen jälkeen tulosta $k$ riviä, joista jokaisella on kaksi lukua, $a$ ja $b$, jotka tarkoittavat että tämä operaatio poisti kaaret $a$ ja $b$. Kaaret on numeroitu siinä järjestyksessä missä ne annettiin syötteessä (ensimmäinen kaari on numero 1).

Rajat

• $1 \le n \le 10^5$
• $1 \le m \le 10^6$
• $0 \le c \le 10^9$
• $1 \le u, v \le n, u \neq v$

Esimerkki

Syöte:

4 3
1 2 20
2 3 10
3 4 30

Tuloste:

40
1
2 3

Syöte:

3 3
1 2 1
2 3 2
3 1 3

Tuloste:

5
1
2 3

Syöte:

5 4
1 2 1
1 3 10
1 4 100
1 5 1000

Tuloste:

1111
2
1 2
3 4

Syöte:

6 4
1 2 1000000
1 3 1000000
4 5 1000000
4 6 1000000

Tuloste:

4000000
2
1 2
3 4