#include<stdio.h>
#include<algorithm>
using namespace std;
struct muchie{int a,b,c,e;};
muchie mu[400001];
int rad[200001];
int radacina(int nod){
    if(rad[nod]==nod)
        return nod;
    else{
        rad[nod]=radacina(rad[nod]);
        return rad[nod];
    }
}
bool cmp(muchie a,muchie b){
    if(a.c<b.c)
        return true;
    else
        return false;
}
int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,i,cost=0,nr=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&mu[i].a,&mu[i].b,&mu[i].c);
    }
    for(i=1;i<=n;i++)
        rad[i]=i;
    sort(mu+1,mu+m+1,cmp);
    for(i=1;i<=m;i++){
        rad[mu[i].a]=radacina(mu[i].a);
        rad[mu[i].b]=radacina(mu[i].b);
        if(rad[mu[i].a]!=rad[mu[i].b]){
            cost+=mu[i].c;
            if(rad[mu[i].b]>rad[mu[i].a])
                rad[mu[i].b]=rad[mu[i].a];
            else
                rad[mu[i].a]=rad[mu[i].b];
            mu[i].e=1;
            nr++;
        }
    }
    printf("%d\n%d\n",cost,nr);
    for(i=1;i<=m;i++)
        if(mu[i].e==1)
            printf("%d %d\n",mu[i].a,mu[i].b);
    return 0;
}