h2. Date de ieşire

Fisierul de iesire $apm.out$ va contine pe prima linie costul arborelui partial de cost minim. Pe urmatoarea linie se va gasi numarul de muchii din arbore. Si pe urmatoarele linii pana la sfarsitul fisierului de iesire se vor tipari, individual pe fiecare linie,cele doua nodurile legate de fiecare muchie din arbore.

Fisierul de iesire $apm.out$ va contine pe prima linie costul arborelui partial de cost minim. Pe a doua linie se va gasi numarul de muchii din arborele partial selectat. Fiecare din urmatoarele linii, pana la sfarsitul fisierului de iesire, va contine cate doua numere naturale, capetele unei muchii ce apartine arborelui solutie. Muchiile pot fi afisate in orice ordine. Daca sunt mai multe solutii corecte se poate afisa oricare.

h2. Restricţii

* $1 ≤ N ≤ 200.000$
* $1 ≤ M ≤ 400.000$
* $-1.000 ≤ C ≤ 1.000$
* Pentru $20%$ din teste $N,M ≤ 20$
* Pentru inca $20%$ din teste $N ≤ 800$ si $M ≤ 1.500$

* $1 ≤ N ≤ 200 000$
* $1 ≤ M ≤ 400 000$
* $-1 000 ≤ C ≤ 1 000$
* Pentru $20%$ din teste $N, M ≤ 20$
* Pentru inca $20%$ din teste $N ≤ 800$ si $M ≤ 1 500$

h2. Exemple