#include<fstream>
#include<algorithm>
#include<cstring>
#define x first
#define y second.first
#define z second.second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int v[800010],n,m,i,j,k,X,Y,Z,cost;
pair <int,pair<int,int> > p[800010];
pair <int,int> s[800010];
/*
    Coded by Emanuel Nrx'@company
*/
int rad(int nod){
    if(v[nod] > 0)
        return rad(v[nod]);
    else
        return nod;
}
/*
    Coded by Gherone'@forces
*/
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>X>>Y>>Z;
        p[2*i-1].x=Z;
        p[2*i-1].y=X;
        p[2*i-1].z=Y;
        p[2*i].x=Z;
        p[2*i].y=Y;
        p[2*i].z=X;
    }
    sort(p+1,p+2*m+1);
    memset(v, -1, sizeof(v));
    for(i=1;i<=2*m;i++){
        X=rad(p[i].y);
        Y=rad(p[i].x);
        if(X!=Y){
            switch(X-Y>=0)
            {
                case 1:{v[X]-=v[Y];v[Y]=X;break;}
                case 2:{v[Y]-=v[X];v[X]=Y;break;}
            }
            k++;
            s[k].x=X;
            s[k].second=Y;
            cost+=p[i].x;
        }
    }
    fout<<cost<<"\n"<<k<<"\n";
    for(i=1;i<=k;i++)
        fout<<s[i].x<<" "<<s[i].second<<"\n";
    return 0;
}