#include<fstream>
#define lim 400007
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int vec[lim],cnt,a,b,T[lim],i,n,m;

struct cub{
    long long x,y;
    short int c;
};
cub q[lim];
struct  cmp{
    bool operator ()(const cub a,const cub b)const{
        return a.c<b.c;
    }
};
int FT(int x){
	if(T[x]<0)
		return x;
	T[x]=FT(T[x]);
	return T[x];
	
}

int main () {
	
	f>>n>>m;
	
	for(i=1;i<=n;++i)
		T[i]=-1;
	
	
	for(i=1;i<=m;++i){
		f>>q[i].x>>q[i].y>>q[i].c;
	}
	
	
	sort(q+1,q+1+n,cmp());
	int ans=0;
	for(i=1;i<=m;++i){
		a=FT(q[i].x);
		b=FT(q[i].y);
		
		if(a!=b){
			T[a]+=T[b];
			T[b]=a;
			ans+=q[i].c;
			vec[++cnt]=i;
		}
		
	}
	g<<ans<<"\n";
	g<<cnt<<"\n";
	
	for(i=1;i<=cnt;++i)
		g<<q[vec[i]].x<<" "<<q[vec[i]].y<<"\n";
	return 0;
}