#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,q,f;
 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;
    ok=1;
    s=0;
    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;
}