#include<fstream>
#define M 200000000
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int a[20000][20000],n,m,viz[200000],s,t[200000];
void umple()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i-j)
			a[i][j]=M;
}
void citire()
{
	int x,y,c;
	
	while(f>>x>>y>>c)
		a[x][y]=c;
}
void solve()
{
	int lin,col,i,j,mini;
	viz[1]=1;
	for(int k=1;k<=n-1;k++)
	{
		mini=M;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if((viz[i]-viz[j])==1&&mini>a[i][j])
				{
					mini=a[i][j];
					lin=i;col=j;
				}
		viz[col]=1;
		t[col]=lin;s+=a[lin][col];
		
	}
}
void afisare()
{
	g<<s<<'\n'<<n-1<<'\n';
	for(int i=2;i<=n;i++)
		g<<t[i]<<" "<<i<<'\n';
	
}
int main()
{
	f>>n>>m;
	umple();
	citire();
	solve();
	afisare();
	return 0;
}