#include <iostream>
#include <cstdio>
#include <vector>
#define nmax 200005
#define kmax 400005
#include <algorithm>
#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],k;
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;
}
struct coord{
 int a,b,c;
};
bool cmp(const coord A, const coord B){
    return A.c<B.c;
}
coord r[kmax];
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;
        r[i].a=x;r[i].b=y;r[i].c=z;
    }
    sort(r+1,r+m+1,cmp);
    for(i=1;i<=n;i++) T[i]=i;
//     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);
    ok=1;
    s=0;
//    for(i=1;i<=m;i++)
//         cout << c[i]<<' ';
    int rad;
    while(ok){
            ok=0;
         for(i=1;i<=m;i++)
            if(!v[i]&&Well(r[i].a,r[i].b)){
                T[fix(r[i].a)]=T[fix(r[i].b)];
                v[i]=1;
                ok=1;
                s+=r[i].c;
                sol[++sol[0]]=r[i].a;
                sol[++sol[0]]=r[i].b;
                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;
}