#include <iostream>
#include <stdio.h>
using namespace std;
long a,b,c,n,m,i,ct,k,j,nr1,nr2,ln[200001],col[200001];
struct muchie {int cost; int x; int y; }v[400001];
void sort(long l,long r)
{int p,u,mij,z;
p=l;u=r;mij=v[(p+u)/2].cost;
do{
while(v[p].cost<mij)p++;
while(v[u].cost>mij)u=u-1;
if(p<=u){z=v[p].cost;v[p].cost=v[u].cost;v[u].cost=z;
		z=v[p].x;v[p].x=v[u].x;v[u].x=z;
		z=v[p].y;v[p].y=v[u].y;v[u].y=z;
		p++;
		u=u-1;
		}
}
while(p<=u);
if(p<r)sort(p,r);
if(l<u)sort(l,u);
}
int main()
{long l[200001],sol;
FILE *f,*g;
f=fopen("apm.in","r");
g=fopen("apm.out","w");
fscanf(f,"%ld%ld",&n,&m);
for(i=1;i<=m;i++)
	{fscanf(f,"%ld%ld%ld\n",&a,&b,&c);
	v[i].x=a;
	v[i].y=b;
	v[i].cost=c;
	}
for(i=1;i<=n;i++) l[i]=i;
sort(1,m);
ct=0;
k=0;
sol=0;
i=1;
while(k<n-1)
{
	if(l[v[i].x]!=l[v[i].y]){ct=ct+v[i].cost; k++;
					sol++; ln[sol]=v[i].x; col[sol]=v[i].y;
					nr1=l[v[i].x]; nr2=l[v[i].y];
					for(j=1;j<=n;j++)
						if(l[j]==nr2) l[j]=nr1;
							}
	i++;
}
fprintf(g,"%ld\n",ct);
fprintf(g,"%ld\n",sol);
for(i=1;i<=sol;i++)
	fprintf(g,"%ld %ld\n",ln[i],col[i]);
return 0;
fclose(f);
fclose(g);
}