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

#define pb push_back

using namespace std;

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

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

vector <muchie> 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;
	while(m--){
		in>>aux.x>>aux.y>>aux.c;
		e.pb(aux);
	}
}

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

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