#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;
int gr[400100],x[400100],y[400100],c[400100];
int n,m,dist,poz[400100];
vector<int> sol;
int grupa(int i){
	if (gr[i] == i) 
		return i;
	gr[i] = grupa(gr[i]);
	return gr[i];
}
void reuniune(int i,int j){
	gr[grupa(i)] = grupa(j); 
}
inline bool comp(int i,int j){
	return(c[i]<c[j]);
}
int main(){
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	int i;
	for(i=1;i<=m;i++)
	{
		f>>x[i]>>y[i]>>c[i];
		poz[i]=i;
	}
	for(i=1;i<=n;++i) 
		gr[i]=i;
	//sortez pozitiile in functie de cost
	sort(poz+1,poz+m+1,comp);
	
	for(i=1;i<=m;i++)
	{
		//daca nu sunt in acelasi arbore le unesc
		if (grupa(x[poz[i]]) != grupa(y[poz[i]])){
			dist += c[poz[i]];
			reuniune(x[poz[i]],y[poz[i]]);
			sol.pb(poz[i]);
		}
	}
	g<<dist<<"\n";
	g<<n-1<<"\n";
	for(i=0;i<n-1;i++)
		g<<x[sol[i]]<<" "<<y[sol[i]]<<"\n";
	return 0;
}