#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,cost_sortare[N+1],comp_conexa[N+1];
vector <int> arbore;
int 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(comp_conexa[i]==i)
		return i;
	comp_conexa[i]=grupa(comp_conexa[i]);
	return comp_conexa[i];
}


void reuniune(int i,int j)
{
	comp_conexa[grupa(i)]=grupa(j);
}


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


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