#include <fstream>
#include <algorithm>
#include <vector>

#define pb push_back

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

const int M=410000;

struct muchie{
	int x,y,c;
};

muchie[N] e,rez;
int n,m,* v;

bool comp(muchie a, muchie b){
	if(a.c<b.c)
		return true;
	return false;
}

int getroot(int & x){
	int ant,root,cx=x;
	for(;v[x]!=x;x=v[x]);
	root=x;
	x=cx;
	ant=cx;
	for(;v[x]!=x;x=v[x]){
		v[ant]=root;
		ant=x;
	}
	return root;
}

void read(){
	muchie aux;
	in>>n>>m;
	for(int i=1;i<=m;++i){
		in>>aux.x>>aux.y>>aux.c;
		e[i]=aux;
	}
}

void solve(){
	int i,adaug=0,c=0,x,y;
	sort(&e[1],&e[m+1],comp);
	v=new int[n+1];
	for(i=1;i<=n;++i)
		v[i]=i;
	for(i=1;i<=m;++i){
		if(getroot(e[i].x)==getroot(e[i].y))
			continue;
		v[getroot(e[i].x)]=getroot(e[i].y);
		adaug++;
		rez[adaug]=e[i];
		c+=e[i].c;
	}
	out<<c<<"\n"<<n-1<<"\n";
	for(i=1;i<=n-1;++i){
		out<<rez[i].x<<" "<<rez[i].y<<"\n";
	}
}

int main(){
	read();
	solve();
	return 0;
}