#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define nmax 200005
#define mmax 400005
int n,m,t[nmax],ct,nr,r1,r2;
struct muchie
{
	int x,y;
	int cost;
} v[mmax];
struct rez
{
	int ind1;
	int ind2;
} r[nmax];
bool cmp(muchie a,muchie b)
{
	return a.cost<b.cost;
}
/*int rad(int x)
{
	if(t[x]==0)
		return x;
	else
		return rad(t[x]);
}*/
int rad(int x)
{
	while(t[x]!=0)
		x=t[x];
	return x;
}
void citire()
{
	f>>n>>m;
	for(int i=1;i<=m;i++)
		f>>v[i].x>>v[i].y>>v[i].cost;
}
int main()
{
	citire();
	sort(v+1,v+m+1,cmp);
	int i=1;int val=0;
	while(nr!=n-1)
	{
		r1=rad(v[i].x);
		r2=rad(v[i].y);
		if(r1!=r2)
		{
			ct+=v[i].cost;
			nr++;
			r[++val].ind1=v[i].x;
			r[val].ind2=v[i].y;
			if(r1<r2)
				t[r1]=r2;
			else
				t[r2]=r1;
		}
		i++;
	}
	g<<ct<<'\n'<<n-1<<'\n';
	for(i=1;i<=n-1;i++)
		g<<r[i].ind1<<' '<<r[i].ind2<<'\n';
	return 0;
}