#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, cc[200001], s, nr, g[200000], k;

struct muchie{
    int x, y, c;
}v[400001];

bool verif(muchie a, muchie b){
    return a.c < b.c;
}

void afis(){
    fout<<s<<'\n'<<nr<<'\n';
    for(int i=1; i<=nr; i++)
        fout<<v[g[i]].x<<' '<<v[g[i]].y<<'\n';
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++){
        fin>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1, v+m+1, verif);
    for(int i=1; i<=n; i++)
        cc[i]=i;
    int mi, ma;
    while(nr < n-1){
        if(cc[v[k].x] != cc[v[k].y]){
            g[++nr]=k;
            s+=v[k].c;
        }
        if(cc[v[k].x] < cc[v[k].y]){
            mi=cc[v[k].x]; ma=cc[v[k].y];
        }
        else{
            ma=cc[v[k].x]; mi=cc[v[k].y];
        }
        for(int i=1; i<=n; i++)
            if(cc[i] == ma) cc[i]=mi;
        k++;
    }
    afis();
    return 0;
}