#include<iostream.h>
#include<fstream.h>
ifstream fin("apm.in");
ofstream fout("apm.out");
using namespace std;
int m,a[100][100],n,c[100],s[100],cost;
const float Pinfinit=1.e20;
struct nod
	{
		int x,y,c;
	};
	nod g[100];
void cit()
{
	int i,j,o;
	fin>>n>>m;
	for(i=1;i<=m;i++)
		fin>>g[i].x>>g[i].y>>g[i].c;
	for(i=1;i<=n;i++)
		c[i]=i;
}
void sortareMuchii(int st, int dr)
{
	int i,j;
	nod e;
	if(st<dr)
	{
		e=g[st];
		i=st;
		j=dr;
		while(i<j)
		{
			while(i<j && g[j].c>=e.c)
				j--;
			g[i]=g[j];
			while(i<j && g[i].c<=e.c)
				i++;
			g[j]=g[i];
		}
		g[i]=e;
		sortareMuchii(st,i-1);
		sortareMuchii(i+1,dr);
	}
}
void kruskal()
{
	int i,nrmsel=0,min,max,j;
	for(i=1;nrmsel<n-1;i++)
		if(c[g[i].x]!=c[g[i].y])//muchia i nu formeaza cicluri deja selectate
		{
		//	nrmsel++;
		//	a[++nrmsel]=i;//selectez muchia i
			if(c[g[i].x]<c[g[i].y])//unfic componentele conexe ale extremitatilor
			{
				min=c[g[i].x];
				max=c[g[i].y];
			}
			else
			{
				min=c[g[i].y];
				max=c[g[i].x];
			}
			for(j=1;j=n;j++)
				if(c[j]==max)
					c[j]=min;
		}
}
void afisare()
{
	int i;
	fout<<cost<<'\n';
	fout<<n-1<<'\n';
	for(i=1;i<n;i++)
		fout<<a[i][1]<<" "<<a[i][2]<<'\n';
}
void kruskal2()
{
	int i,j,k=1;
	s[g[1].x]=1;
	s[g[1].y]=1;
	a[1][1]=g[1].x;
	a[1][2]=g[1].y;
	cost=g[1].c;
	for(i=2;i<=m;i++)
		if(s[g[i].x]!=1 && s[g[i].y]==1)
		{
			s[g[i].x]=1;
			cost=cost+g[i].c;
			k++;
			a[k][1]=g[i].x;
			a[k][2]=g[i].y;
		}
		else
			if(s[g[i].x]==1 && s[g[i].y]!=1)
			{
				s[g[i].y]=1;
				cost=cost+g[i].c;
				k++;
				a[k][1]=g[i].y;
				a[k][2]=g[i].x;
			}
}
	
int main()
{
	cit();
	sortareMuchii(1,m);
	kruskal2();
	afisare();
	return 0;
	
}