#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");


const int N=1e5;
int cost_minim,indice[N+1],gr[N+1];
vector <int> varfuri_cost_minim;
int n,m,x[N+1],y[N+1],c[N+1];


bool cmp(int i,int j)
{
	return (c[i]<c[j]);
}


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);
}


void Kruskal()
{
	for(int i=1; i<=n; i++)
		gr[i]=i;
	sort(indice+1,indice+m+1,cmp);
	for(int i=1; i<=m; i++)
	{
		if(grupa(x[indice[i]])!=grupa(y[indice[i]]))
		{
			cost_minim=cost_minim+c[indice[i]];
			reuniune(x[indice[i]],y[indice[i]]);
			varfuri_cost_minim.push_back(indice[i]);
		}
	}
}


int main()
{
	f>>n>>m;
	for(int i=1; i<=m; i++)
	{
		f>>x[i]>>y[i]>>c[i];
		indice[i]=i;
	}
	Kruskal();
	//sort(varfuri_cost_minim.begin(),varfuri_cost_minim.end());
	g<<cost_minim<<endl;
	g<<n-1<<endl;
	for(int i=0; i<n-1; i++)
		g<<x[varfuri_cost_minim[i]]<<" "<<y[varfuri_cost_minim[i]]<<endl;
	f.close();
	g.close();
	return 0;
}