#include<fstream>
#include<algorithm>
#include<vector>
#define lim 400020
using namespace std;
int n,m,c,T[lim/2],a,b,i,j,nr,viz[lim],cost,k[lim];
ifstream f("apm.in");
ofstream g("apm.out");
vector<int>muc;
struct muchii{
	long long x,y;
	short int c;
};
muchii v[lim];
/*int tata(int x){
	int y=x;
	while(T[y]>0)
		y=T[y];
	return y;
}*/
/*void lipeste (int a,int b){
	if(-T[a]>=-T[b]){
		T[a]=T[b]+T[a];
		T[b]=a;
	}
	else{
		T[b]=T[b]+T[a];
		T[a]=b;
	}
}*/
int tata(int x){
	if(T[x]<0)
		return x;
	T[x]=tata(T[x]);
	return T[x];
}
struct cmp {
	bool operator () (const muchii e , const muchii r) const{
		return e.c<r.c;
	}
};
int main (){
	f>>n>>m;
	for(i=1;i<=m;i++)
		f>>v[i].x>>v[i].y>>v[i].c;
	for(i=1;i<=n;i++)
		T[i]=-1;
	sort(v+1,v+m+1,cmp());
	for(i=1;  i<=m ;i++ ){
		
		a=tata(v[i].x);
		b=tata(v[i].y);
		if(a!=b){
			k[++nr]=i;
			cost+=v[i].c;
			T[a]=b;
		}
		
	}
	g<<cost<<"\n";
	g<<nr<<"\n";
	for(i=1;i<=nr;i++){
		g<<v[k[i]].x<<" "<<v[k[i]].y<<"\n";
	}
	return 0;
}