#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct PAIR{ //structura pentru muchii

    int muchieX, muchieY, costMuchie;

}PAIR;

PAIR P;

ifstream fin("date.txt");
ofstream fout("apm.out");

int nrNoduri, nrMuchii, costArborePartial, nrMuchiiArborePartial, *vectorTati, *rang;
vector <PAIR> muchii;
bool *vizitatMuchii;

int Radacina(int nod){

    int radacinaNod = nod;

    while ( vectorTati[radacinaNod] != radacinaNod ) //caut radacina nodului
                radacinaNod = vectorTati[radacinaNod];

    while ( vectorTati[nod] != nod ){ //actualizez vectorul de tati cu radacina gasita ( aplic compresia drumurilor )
         int aux = vectorTati[nod];
         vectorTati[nod] = radacinaNod;
         nod = aux;
    }

    return radacinaNod;

}

void Unire(int radacinaX, int radacinaY){ //leg radacinile a  doua componente conexe

    if ( radacinaX != radacinaY ){ //in caz ca radacinile sunt diferite -> avem doua submultimi ( componente conexe ) diferite

            if(rang[radacinaX] > rang[radacinaY])  //unesc multimea cu rang mai mic de cea cu rang mai mare
                        vectorTati[radacinaY] = radacinaX;

            else
                vectorTati[radacinaX] = radacinaY;


            if( rang[radacinaX] == rang[radacinaY] ) //in caz ca rangurile erau egale atunci cresc rangul noii multimi cu 1
                                    rang[radacinaY]++;
    }

}

int cmp(PAIR X, PAIR Y){

    return  X.costMuchie < Y.costMuchie;

}

void kruskal(){ //initial toate nodurile sunt izolate, deci apm - ul este creat pe parcurs prin reunirea subarborilor

    int nrComponenteConexe = nrNoduri; //nrComponenteConexe reprezinta nr nodurilor grafului

    for ( int i = 1; i <= nrNoduri; i++){  //se pleaca de la ideea de arbore izolat deci fiecare nod se are radacina pe el insusi
                    vectorTati[i] = i;
                    rang[i] = 1;
    }

    costArborePartial = 0 , nrMuchiiArborePartial = 0;

    int lim = muchii.size();

    for(int i = 0; i < lim && nrComponenteConexe > 1 ; i++){ //mergem pe fiecare muchie ( cat timp mai avem muchii si nu am parcurs toate nodurile )

        int radacinaX = Radacina(muchii[i].muchieX) , radacinaY = Radacina(muchii[i].muchieY);

		if ( radacinaX != radacinaY ){ //daca radacinile difera inseamna ca avem componente conexe diferite

			vizitatMuchii[i] = true;

			costArborePartial += muchii[i].costMuchie;
			nrMuchiiArborePartial++;

            Unire(radacinaX,radacinaY);

            nrComponenteConexe--; //scadem nr componentelor conexe ( efectiv am unit 2 noduri, deci vom scadea nr de componente conexe )
		}
    }
}

int main(){

    if ( !fin ){
        cout << "\nEroare la deschiderea fisierului !\n";
        exit(-1);
    }

    fin >> nrNoduri;

    vectorTati = NULL;

    vectorTati = new int[nrNoduri + 5];
    rang = new int[nrNoduri + 5];

    if (!vectorTati || !rang){
        cout << "\nEroare la alocarea dinamica !\n";
        exit(-1);
    }

     fin >> nrMuchii;

     vizitatMuchii = new bool[nrMuchii + 5];

     if (!vizitatMuchii){
         cout << "\nEroare la alocarea dinamica !\n";
         exit(-1);
     }

     for (int i = 0; i < nrMuchii; i++) {

        fin >> P.muchieX >> P.muchieY >> P.costMuchie;

        muchii.push_back(P);

        vizitatMuchii[i] = false;

     }

     sort(muchii.begin(),muchii.end(),cmp); //sortez muchiile in ordine descrescatoare dupa cost

     kruskal();

     cout << costArborePartial << "\n" << nrMuchiiArborePartial << "\n";

     for ( int i = 0; i < nrMuchii; i++)
           if ( vizitatMuchii[i] )
                    cout << muchii[i].muchieX << " " << muchii[i].muchieY <<"\n";


    return 0;

}