#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
long n,m,i,j,minim,maxim,nrm;
long cost;
typedef struct {int x,y,cost;} VARF;
VARF G[200001];
int A[200001],C[200001];

bool operator <(const VARF &a, const VARF &b)
{
	if (a.cost<b.cost)
		return 1;
	return 0;
}

int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	
	f>>n>>m;
	for (i=1;i<=m;i++)
		f>>G[i].x>>G[i].y>>G[i].cost;
	for (i=1;i<=n;i++)
		C[i]=i;
	sort(G+1,G+m+1);
	nrm=0;
	i=1;
	while (nrm<n-1)
	{
		if (C[G[i].x]!=C[G[i].y])
		{
			nrm++;
			A[nrm]=i;
		}
		if (C[G[i].x]<C[G[i].y])
		{
			minim=C[G[i].x];
			maxim=C[G[i].y];
		}
		else
		{
			minim=C[G[i].y];
			maxim=C[G[i].x];
		}
		for (j=1;j<=n;j++)
			if (C[j]==maxim)
				C[j]=minim;
		i++;
	}
	cost=0;
	for (i=1;i<n;i++)
		cost+=G[A[i]].cost;
	g<<cost<<endl;
	g<<n-1<<endl;
	for (i=1;i<n;i++)
		g<<G[A[i]].x<<" "<<G[A[i]].y<<endl;
	f.close();
	g.close();
	return 0;
}