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

struct mu
{
    int a,b,c;
}v[400001] ;
int h[200001],tata[200001];
int cmp(mu x, mu y)
{
    return x.c<y.c;
}
int radacina(int x)
{
    int r=x,y;
    while(r!=tata[r])
    {
        r=tata[r];
    }
    while(x!=tata[x])
    {
        y=x;
        x=tata[x];
        tata[y]=r;
    }
    return r;

}
void uniune(int x,int y)
{
    if(h[x]<h[y]){tata[y]=x;}
    else{if(h[x]==h[y]){h[x]++;tata[y]=x;}else tata[x]=y; }
}

int main()
{freopen("apm.in","r",stdin);
 freopen("apm.out","w",stdout);
int n,m,i,j,a,b,cate=0,cost=0,k=0;
int w[400001];
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
    scanf("%d%d%d",&(v[i].a),&(v[i].b),&(v[i].c) );
}
sort(v,v+m,cmp);
for(i=1;i<=n;i++){h[i]=1;tata[i]=i;}

for(i=0;i<m&&cate<n-1;i++)
{a=radacina(v[i].a);
 b=radacina(v[i].b);
 if(a!=b)
 {
     cate++;
     uniune(a,b);
     w[k]=v[i].a;k++;w[k]=v[i].b;k++;
     cost+=v[i].c;
 }

}
printf("%d\n%d\n",cost,cate );
for(i=0;i<k;i=i+2)
{
    printf("%d %d\n",w[i],w[i+1]);
}




    return 0;
}