#include<fstream>
#define Max 19001
#define Infinit 1001

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,c[Max][Max],s[Max],t[4][Max],smin,k;
void read()
{
	int i,x,y,d;
	fin>>n>>m;
	for(i = 1; i <= n; i++)
	{
		for(x = 1; x <= n; x++)
			c[i][x] = Infinit;
	}
	for(i = 1; i <= m; i++)
	{
		fin>>x>>y>>d;
		c[x][y] = d;
		c[y][x] = d;
	}
fin.close();
}
void afis()
{
	int i;
	fout<<smin<<"\n";
	fout<<k<<"\n";
	for(i = 1; i <= k; i++)
		fout<<t[1][i]<<" "<<t[2][i]<<"\n";
}
void prim()
{
	int i,min,l,j,p;
	for(i = 2; i <= n; i++)
		s[i] = 1;
	for(l = 1; l <= n-1; l++)
	{
		min = Infinit;
		
			for(i = 1; i <= n; i++)
				if(s[i])
				if( min>c[s[i]][i])
				{
					min = c[s[i]][i];
					j = i;
					p = s[i];
				}
				//	fout<<min<<"\n";
				smin+=min;
				k=k+1;
				t[1][k] = j;
				t[2][k] = p;
			for(i = 1; i <= n; i++)
				if(s[i] && c[s[i]][i] > c[j][i])
					s[i] = j;
			s[j] = 0;
	}
}
int main()
{
	read();
	prim();
	afis();

	fout.close();
return 0;

}