#include<stdio.h>
#include<algorithm>
using namespace std;

struct muchie{int a,b,c;}v[400004];

struct lista {int a,b;
                lista *urm;}*sol;

int i,j,k,cost,l,m,n,nr[200002],tip[200040],urm[200040],ult[200040];

int cmp(muchie a,muchie b){

return a.c<b.c;}

void merge(int a,int b){
urm[ult[a]]=b;
ult[a]=ult[b];

int p=b;
do{tip[p]=a;
p=urm[p];
}while(p);
}

int main(){

freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
scanf("%d %d",&n,&m);

for(i=1;i<=n;i++)
        {tip[i]=i;
        ult[i]=i;
        nr[i]=1;
        }

for(i=1;i<=m;i++)
        scanf("%d %d %d",&v[i].a,&v[i].b,&v[i].c);

sort(v+1,v+1+m,cmp);

for(i=1;i<=m;i++)
        if(tip[v[i].a]!=tip[v[i].b])
                {cost+=v[i].c;
                lista *p=new lista;
                p->a=v[i].a;
                p->b=v[i].b;
                p->urm=sol;
                sol=p;
                k++;
                if(nr[tip[v[i].a]]<nr[tip[v[i].b]])
                merge(tip[v[i].a],tip[v[i].b]);
                else
                merge(tip[v[i].b],tip[v[i].a]);}

printf("%d\n%d\n",cost,k);

lista *p=sol;
for(;p;p=p->urm)
        printf("%d %d\n",p->a,p->b);

return  0;}