#include <fstream>
#include <algorithm>

#include <vector>
#define maxN 200001
#define maxM 400001
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie {int x,y,cost;};
muchie a[maxM];
int v[maxN];
int c[maxN],n,m;

int cond (muchie h1, muchie h2)
{
	if (h1.cost<h2.cost) return 1;
	else return 0;
}


int main()
{
	int i,sel,min,max,s;
	fin>>n>>m;
	for (i=1;i<=m;i++)
		fin>>a[i].x>>a[i].y>>a[i].cost;
	for (i=1;i<=n;i++)
		c[i]=i;
	
	sort(a+1,a+m+1,cond);
	sel=0; s=0;
	for (i=1;s<n-1;i++)
		if (c[a[i].x]!=c[a[i].y])
		{
			sel++;
			v[sel]=i; s=s+a[i].cost;
			if (a[i].x<a[i].y)
			{
				min=a[i].x;
				max=a[i].y;
			}
			else
			{
				min=a[i].x;
				max=a[i].y;
			}
			for (i=1;i<=n;i++)
				if (c[i]==max) c[i]=min;
		}
	
	fout<<s<<'\n'<<sel<<'\n';
	
	for (i=1;i<=sel;i++)
		fout<<a[v[i]].x<<' '<<a[v[i]].y<<'\n';
	
	fout.close();
	return 0;
}