#include<cstdio>
#include<algorithm>
using namespace std;
int t[200100],cost,nr[200100],n,m,nre,arbore[2001000];
struct muchie{
	int e1,e2,c;
};
int radacina(int s){
	int r;
	for(r=t[s];r!=t[r];r=t[r]);
	return r;
}
void update(int e1,int e2){
	if(nr[e1]<nr[e2]){
		t[e1]=e2;
	}
	else
		if(nr[e1]==nr[e2]){
			++nr[e1];
			t[e2]=e1;
		}
		else
			t[e2]=e1;
}
muchie v[400100];
int compare (const muchie &a,const muchie &b){
	return a.c<b.c;
}
int solve(int cost,int j,int i){
	if(j!=n-1){
		if(radacina(v[i].e1)!=radacina(v[i].e2)){
			cost+=v[i].c;
			update(radacina(v[i].e1),radacina(v[i].e2));
			++nre;
			arbore[nre]=i;
			return solve(cost,j+1,i+1);
			
		}
		else{
			return solve(cost,j,i+1);
		}
	}
	else{
		
		return cost;

		
	}
	
}
	
int main(){
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		t[i]=i;
		nr[i]=1;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&v[i].e1,&v[i].e2,&v[i].c);
	}
	sort(v+1,v+m+1,compare);
	printf("%d\n",solve(0,0,1));
	printf("%d\n",n-1);
	for(int i=1;i<n;++i){
		printf("%d %d\n",v[arbore[i]].e1,v[arbore[i]].e2);
	}
	return 0;
}