#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");
int n,m,i,t[200001],k,r1,r2,cmin;
struct nod{
	int a;
	int b;
	int c;
} v[400001];
bool s[400001];
queue <int> a;
int cmp(const void *lhs,const void *rhs)
{
	const nod *a = (const nod *) lhs;
	const nod *b = (const nod *) rhs;
	
	if (a->c > b->c)
		return 1;
	else if (a->c == b->c)
		return 0;
	else
		return -1;
	
   //return return ( *(int*)lhs - *(int*)rhs);	
}
int main(){
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++)
		 fscanf(f,"%d%d%d",&v[i].a,&v[i].b,&v[i].c);
for(i=1;i<=n;i++)
	t[i]=-1;
qsort(v+1, m, sizeof (nod), cmp);	
k=0; i=1; cmin=0;
while(k < n-1){
    if(t[v[i].a] < 0)
		  r1=v[i].a;
	else
	r1=t[v[i].a];
	if(t[v[i].b] < 0)
		  r2=v[i].b;
	else
	r2=t[v[i].b];
	while(t[r1]>0){
		r1=t[r1];
	}
	while(t[r2]>0){
		r2=t[r2];
	}
	if(r1!=r2){
		  if(t[r1] < t[r2] ){
			    t[r1]+=t[r2];
				t[r2]=r1;
		  }
		else { t[r2]+=t[r1];
			   t[r1]=r2;
		}
	k++;
	cmin+=v[i].c;
    s[i]=1;
	a.push(i);
	}
i++;
}
fprintf(g,"%d\n%d\n",cmin,n-1);

while(a.size()>0){
//	if(s[i])
		fprintf(g,"%d %d\n",v[a.front()].a,v[a.front()].b);
		a.pop();
}
	
return 0;	
}