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

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

int n, m, cc[400005], s, nr, g[400005], k, rg[400005];

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

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 grupa(int i){
    if(cc[i] == i) return i;
    else{
        int rez = grupa(cc[i]);
        cc[i]=rez;
        return rez;
    }
}

void unire(int x, int y){
    if(rg[x] < rg[y]) cc[x]=y;
    else 
    if(rg[x] > rg[y]) cc[y]=x;
    else{
        cc[x]=y;
        rg[y]++;
    }
}

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;
    for(int i=1; i<=m; i++){
        if(grupa(v[i].x) != grupa(v[i].y)){
            int x1=grupa(v[i].x), y1=grupa(v[i].y);
            unire(x1, y1);
            g[++nr]=i;
            s+=v[i].c;
        }
    }
    afis();
    return 0;
}