#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

#define Nmax 400002

struct nod{

    int x;
    int y;
    int cost;

} Arb[Nmax];

int grupe[Nmax];
int indice[Nmax/2];
vector < pair <int,int> > lista(Nmax/2);

int N, M, cost_f;
int a, b, c;

void citire(){

    ifstream f("apm.in");

    f >> N >> M;

    for(int i = 1; i <= M; i++){

        f >> Arb[i].x >> Arb[i].y >> Arb[i].cost;
        indice[i] = i;
    }

    for(int i = 1; i <= N; i++)
        grupe[i] = i;

    f.close();
}

int cmp(nod a, nod b){

    return a.cost < b.cost;
}

int gr(int i){

    if(grupe[i] == i)
        return i;

    else{
            grupe[i] = gr(grupe[i]);
            return grupe[i];
        }
}

int reuniune(int i, int j){

    grupe[gr(i)] = gr(j);
}

void Kruskal(){

    for(int i = 1, l = 1; i <= M; i++){

        if(gr(Arb[indice[i]].x) != gr(Arb[indice[i]].y)){

           cost_f += Arb[indice[i]].cost;
           reuniune(Arb[indice[i]].x, Arb[indice[i]].y);
           lista[l].first =  Arb[indice[i]].x,
           lista[l++].second = Arb[indice[i]].y;
        }
    }
}

void afis(){

    ofstream g("apm.out");

    g << cost_f << "\n";
    g << N-1 << "\n";

    for(int i = 1; i < N; i++)
        g << lista[i].first << " " << lista[i].second << "\n";
}

int main(){

    citire();
    sort(Arb + 1, Arb + 1 + M, cmp);
    Kruskal();
    afis();

    return 0;
}