#include<stdio.h>
#include<algorithm>
#include<vector>
#define fs first
#define sc second
using namespace std;
typedef pair<int, int> hh;
typedef pair<int, hh> gg;
vector <pair <int, pair<int,int> > > nr;
int sol[200100],tata[200100];
int dad(int x){
	if(x==tata[x])
		return x;
	return tata[x]=dad(tata[x]);
}
int main(){
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	int n,m,i,aux,sum,t1,t2,a,b,c;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;++i){
		scanf("%d%d%d",&a,&b,&c);
		nr.push_back(gg(c,hh(a,b)));
	}
	sort(nr.begin(),nr.end());
	for(i=0;i<=n;++i)
		tata[i]=i;
	sum=aux=i=0;
	while(aux<n-1){
		t1=dad(nr[i].sc.fs);
		t2=dad(nr[i].sc.sc);
		if(t1!=t2){
			sum+=nr[i].fs;
			sol[++aux]=i;
			tata[t1]=t2;
		}
		++i;
	}
	printf("%d\n%d\n",sum,n-1);
	for(i=1;i<n;++i)
		printf("%d %d\n",nr[sol[i]].sc.fs,nr[sol[i]].sc.sc);
	fclose(stdin);
	fclose(stdout);
	return 0;
}