#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

long nrv,vfmin,i,j,n,m,r,x,y,cost,total;
long G[20001][20001];
long P[20001],Z[20001];
long cmin[20001];

int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	
	f>>n>>m;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			G[i][j]=10000;
	
	for (i=1;i<=m;i++)
	{
		G[i][i]=0;
		f>>x>>y>>cost;
		G[x][y]=G[y][x]=cost;
	}
	
	for (i=1;i<=n;i++)
	{
		cmin[i]=G[n][i];
		P[i]=n;
		Z[i]=1;
	}
	Z[n]=0;
	P[n]=0;
	nrv=n-1;
	
	while (nrv)
	{
		cost=10000;
		for (i=1;i<=n;i++)
			if (Z[i] && cost>cmin[i])
			{
				cost=cmin[i];
				vfmin=i;
			}
		Z[vfmin]=0;
		nrv--;
		for (i=1;i<=n;i++)
			if (Z[i] && G[i][vfmin]<cmin[i])
			{
				P[i]=vfmin;
				cmin[i]=G[i][vfmin];
			}
	}
	total=0;
	for (i=1;i<=n;i++)
		if (i!=r)
		total+=G[i][P[i]];
	g<<total<<endl;
	g<<n-1<<endl;
	for (i=1;i<=n;i++)
		if (i!=n)
			g<<P[i]<<" "<<i<<endl;
	f.close();
	g.close();
	return 0;
}