#include <iostream>
#include <cstdio>
#include <vector>
#define nmax 200005
#define kmax 400005
#include <queue>
using namespace std;
vector<int>G[nmax];
short st[kmax],dr[kmax],c[kmax],v[kmax],sol[kmax];
int n,m,T[nmax];
inline int fix(int x){
 int rad;
 rad=x;
 while(rad!=T[rad])
    rad=T[rad];
    T[x]=rad;
    return rad;
}
inline bool Well(int x,int y){
 if(T[fix(x)] == T[fix(y)]) return 0;
 return 1;
}
int main(){
    int i,x,y,z,ok,s;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        st[i]=x;dr[i]=y;c[i]=z;
    }
    do{
        ok=0;
         for(i=1;i<m;i++)
         if(c[i] > c[i+1]){
            swap(c[i],c[i+1]);
            swap(st[i],st[i+1]);
            swap(dr[i],dr[i+1]);
            ok=1;
         }
    }while(ok);
    for(i=1;i<=n;i++) T[i]=i;
    ok=1;
    s=0;
    int rad;
    while(ok){
            ok=0;
//            for(i=1;i<=n;i++){
//                    rad=i;
//                while(rad!=T[rad]) rad=T[rad];
//              T[i]=rad;
//            }
        for(i=1;i<=m;i++)
            if(!v[i]&&Well(st[i],dr[i])){
                T[fix(st[i])]=T[fix(dr[i])];
                v[i]=1;
                ok=1;
                s+=c[i];
                sol[++sol[0]]=st[i];
                sol[++sol[0]]=dr[i];
            //cout << st[i]<<' '<<dr[i]<<' '<<c[i]<<'\n';
                break;
            }
    }
    cout << s<<'\n'<<sol[0]/2<<'\n';
    for(i=1;i<=sol[0];i+=2)
        cout<<sol[i]<<' '<<sol[i+1]<<'\n';
    return 0;
}