#include<cstdio>
#include<algorithm>
#define maxm 400005
#define maxn 200005
using namespace std;
struct muchie{
    int x,y,c;
};
muchie V[maxm];
 
int compare(const muchie &A,const muchie &B){
    return A.c<B.c;
}
int nrs,n,m,sol[maxn],t[maxn],nr[maxn],cost;
void update(int e1,int e2){
    if(nr[e1]==nr[e2]){
        nr[e1]+=nr[e2];
        t[e2]=e1;
    }
    else
        if(nr[e1]>nr[e2]){
            nr[e2]+=nr[e1];
            t[e1]=e2;
        }
        else{
            nr[e1]+=nr[e2];
            t[e2]=e1;
        }
}
int radacina (int nod){
int    r=t[nod];
    for(;r!=t[r];r=t[r]);
    return r;
}
 
int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d", &n,&m);
    for(int i=1;i<=n;++i){
        t[i]=i;
        nr[i]=1;
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&V[i].x,&V[i].y,&V[i].c);
    }
    sort(V+1,V+m+1,compare);
    for(int i=1;i<=m && nrs!=n-1;++i){
        if(radacina(V[i].x)!=radacina(V[i].y)){
            update(radacina(V[i].x),radacina(V[i].y));
            cost+=V[i].c;
            ++nrs;
            sol[nrs]=i;
        }
    }
    printf("%d\n%d\n",cost,nrs);
    for(int i=1;i<=nrs;++i){
        printf("%d %d\n",V[sol[i]].x,V[sol[i]].y);
    }
    return 0;
 
}