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

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

int sol[400002];
int i,p,k,cost=0,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];
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;
                k++;
                sol[k]=i;
                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);

for(i=1;i<=k;i++)
        printf("%d %d\n",v[sol[k]].a,v[sol[k]].b);

return  0;}