#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

#define MAX 400005
int c[MAX];

bool sortHow(int i,int j){
   	return (c[i]<c[j]);
}

int root(int x, int arb[]){
	if(arb[x]==x) return x;
	arb[x]=root(arb[x], arb);
    return arb[x];	
}

void reuniune(int x, int y,int rng[],int arb[]){
	if(rng[x]>rng[y])  arb[y]=x;
	else  arb[x]=y;
	
	if(rng[x]==rng[y]) rng[y]++;
}

int main(){
	ifstream in("apm.in");
	FILE *out=fopen("apm.out","w");
	
	int n, m, i, cost=0;
	in>>n>>m;
	int a[m+1], b[m+1], rng[n+1], arb[n+1], who[m+1], apm[n-1], j=0;
    
	for(i=1;i<=m;i++){
		in>>a[i]>>b[i]>>c[i];
		who[i]=i;
	}
	
	for(i=1;i<=n;i++){
		arb[i]=i;
		rng[i]=1;
	}
	
	sort(who+1,who+m+1,sortHow);
	
	for(i=1;i<=m;i++){
	   if(root(a[who[i]],arb)!=root(b[who[i]],arb))	{
	   	  cost+=c[who[i]];
	   	  reuniune(root(a[who[i]],arb), root(b[who[i]],arb), rng, arb);
	   	  apm[++j]=i;
	   }
   }
	   
	fprintf(out,"%i\n%i\n",cost,n-1);
	for(i=1;i<=n-1;i++) fprintf(out,"%i %i\n",a[apm[i]],b[apm[i]]);   
	
	in.close(); fclose(out);
	return 0;
}