#include <bits/stdc++.h>
#define DIM 200010
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,i,t[DIM],x,y,rx,ry,k,cost,sol[DIM];
struct muchie{
    int x,y,c;
};
muchie v[2*DIM];
bool cmp(muchie &a,muchie &b) {
    return (a.c<b.c);
}
int rad(int nod) {
    while (t[nod]>0)
        nod=t[nod];
    return nod;
}
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++) {
        x=v[i].x, y=v[i].y;
        rx=rad(x), ry=rad(y);
        if (rx!=ry) {
            sol[++k]=i;
            cost+=v[i].c;
            if (rx>ry) {
                t[rx]+=t[ry];
                t[ry]=rx;
            }
            else {
                t[ry]+=t[rx];
                t[rx]=ry;
            }
        }
    }
    fout<<cost<<"\n"<<n-1<<"\n";
    for (i=1;i<=k;i++)
        fout<<v[sol[i]].x<<" "<<v[sol[i]].y<<"\n";
    return 0;
}