#include <fstream>
#include <algorithm>
using namespace std;
int n, m, k, i, ct, t1, t2, tata[400001];
bool viz[400001];
struct muchie {
    int x;
    int y;
    int c;
};
muchie v[400001];
int cmp (muchie x, muchie y)
{
    return x.c<y.c;
}
int parinte (int x)
{
    while (tata[x]>0) {
        x=tata[x];
    }
    return x;
}
ifstream fin ("apm.in");
ofstream fout ("apm.out");

int main () {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>v[i].x>>v[i].y>>v[i].c;
    }

    for (i=1;i<=n;i++) {
        tata[i]=-1;
    }

    sort (v+1, v+m+1, cmp);
    ct=0; i=1; k=0;
    while (k<n-1) {
        t1=parinte(v[i].x);
        t2=parinte(v[i].y);
        if (t1!=t2) {
            if (tata[t1]<tata[t2]) {
                tata[t1]+=tata[t2];
                tata[t2]=t1;
            } else {
                tata[t2]+=tata[t1];
                tata[t1]=t2;
            }
            ct+=v[i].c;
            viz[i]=1;
            k++;
        }
        i++;
    }

    fout<<ct<<'\n';
    fout<<n-1<<'\n';
    for (i=1;i<=m;i++) {
        if (viz[i]==1) {
            fout<<v[i].x<<" "<<v[i].y<<'\n';
        }
    }

    return 0;
}