#include <iostream>
#include <stdio.h>
using namespace std;
int a,b,c,m,n,j,ct,i,ln[300000],col[300000];
struct muchie {int cost; int x; int y; }v[400000];
void sort(int l,int 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()
{int viz[200000],k;
FILE *f,*g;
f=fopen("apm.in","r");
g=fopen("apm.out","w");
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
	{fscanf(f,"%d%d%d\n",&a,&b,&c);
	v[i].x=a;
	v[i].y=b;
	v[i].cost=c;
	}
sort(1,m);
k=1;
ln[k]=v[1].x;col[k]=v[1].y;
viz[v[1].x]=1;
viz[v[1].y]=1;
ct=v[1].cost;

for(i=1;i<n-1;i++)
{
j=1;
while(viz[v[j].x]==viz[v[j].y]) j++;
ct=ct+v[j].cost;
k++; ln[k]=v[j].x; col[k]=v[j].y;
viz[v[j].x]=1;viz[v[j].y]=1;
}
fprintf(g,"%d\n",ct);
fprintf(g,"%d\n",k);
for(i=1;i<=k;i++)
	fprintf(g,"%ld %ld\n",ln[i],col[i]);
fclose(f);
fclose(g);
return 0;
}