#include <fstream>
#include <algorithm>

using namespace std;

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

int t[200010];

struct data{
    int x;
    int y;
    int c;
    bool z;
}v[400010];

bool cmp (const data &a, const data &b) {
    return a.c<b.c;
}

int m,n,cost,i,rx,ry,M;

int rad (int x) {

    while (t[x]>0)
        x=t[x];
    return x;
}

int main () {

    fin>>n>>m;
    for (i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].c;
    sort (v+1,v+m+1,cmp);
    for (i=1;i<=n;i++)
        t[i]=-1;
    for (i=1;i<=m;i++) {
        rx=rad(v[i].x);
        ry=rad(v[i].y);
        if (rx!=ry){
            cost+=v[i].c;
            v[i].z=1;
            M++;
            if (M==n-1)
                break;
            if (t[rx]<=t[ry]) {
                t[rx]+=t[ry];
                t[ry]=rx;
            }else {
                t[ry]+=t[rx];
                t[rx]=ry;
            }
        }
    }

    fout<<cost<<"\n"<<M<<"\n";

    for (i=1;i<=m;i++)
        if (v[i].z)
            fout<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}