#include <stdio.h>
#include <set>

#define mp make_pair

using namespace std;

FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");


struct nod{
int x;
int y;
}sol1[200008];

multiset < pair < int, pair < int, int> > > H;
multiset < pair < int, pair < int, int> > >::iterator it;


int c[200008],r[200008],n,m,i,x,y,z,nrm,nr,sum,x1,x2;

int caut(int k){
if (c[k]!=k)c[k]=caut(c[k]);
return c[k];
}

void bifez(int x,int y){
if (r[x]>r[y])c[y]=x;
else c[x]=y;
if(r[x]==r[y])r[y]++;
}


int main()
{
//freopen("apm.in"," r", stdin);
//freopen("apm.out"," w", stdout);

fscanf(f,"%d%d",&n,&m);
for(i=1;i<=n;i++){c[i]=i;r[i]=1;}
for(i=1;i<=m;i++)
{
fscanf(f,"%d%d%d",&x,&y,&z);
H.insert(mp(z,mp(x,y)));
}
nr=0;
sum=0;
for(it=H.begin();it!=H.end();++it){
x1=caut((*it).second.first);
x2=caut((*it).second.second);

if(x1!=x2){
sum+=(*it).first;
sol1[++nr].x=(*it).second.first;
sol1[nr].y=(*it).second.second;
bifez(x1,x2);
}
}
fprintf(g,"%d\n",sum);
fprintf(g,"%d\n",nr);
for(i=1;i<=nr;i++)
fprintf(g,"%d %d\n",sol1[i].x,sol1[i].y);


fclose(g);
return 0;
}