#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

#define nmax 200005
#define Mmax 400005
#define ll long long

int n, m, t[nmax];
typedef struct {
    int x, y, c;
}camp;
int Apm[nmax][2];
camp Muchie[Mmax];

void citeste(){
    f >> n >> m;
    for(int i=1; i<=m; ++i){
        f >> Muchie[i].x >> Muchie[i].y >> Muchie[i].c;
    }
}

struct cmp{
    bool operator()(camp A, camp B){
        return A.c < B.c;
    }
};

int afla(int x){
    int x2 = x, aux = 0;
    for(; t[x]!=0; x=t[x]);// caut radacina
    while(x2 != x){// marchez multimile de pe drum
        aux = t[x2];
        t[x2] = x;
        x2 = aux;
    }
    return x;
}

void uneste(int x, int y){
    t[x] = y;
}

void rezolva(){
    sort(Muchie+1, Muchie+m+1, cmp());

    int sz = 0; int costApm = 0;
    for(int i=1; i<=m; ++i){
        int X = Muchie[i].x; int Y = Muchie[i].y; int C = Muchie[i].c;
        int radX = afla(X); int radY = afla(Y);
        if (radX == radY) continue;// sunt deja bagate in arbore
        uneste(radX, radY);
        costApm += C;
        Apm[++sz][0] = X; Apm[sz][1] = Y;
    }

    g << costApm << "\n";
    g << n-1 << "\n";
    for(int i=1; i<n; ++i){
        g << Apm[i][0] << " " << Apm[i][1] << "\n";
    }
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}