#include<iostream>
#include<fstream>
#define INF 2001
#define NNN 23100

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

long n,m;
int a[NNN][NNN];
int v[NNN],viz[NNN];
struct nod {long x,y;}ff[NNN];

int main(void){
f>>n>>m;
long x,y,c;
long cost=0;
long i,j;
for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=INF;
for(i=1;i<=m;i++) 
	{
		f>>x>>y>>c;
		a[x][y]=c;
		a[y][x]=c;
	}

v[1]=1;
viz[1]=1;
long vv=1;
while(vv<n)
{
	int mintotal=INF; long poz,pozz,pozzz;
	for(i=1;i<=vv;i++)
		{
			int min=INF;
			for(j=1;j<=n;j++) if(a[v[i]][j]<min && viz[j]==0) {min=a[v[i]][j];poz=j;}//minimu dp fiecare linie
			if(min<mintotal) {mintotal=min;pozz=poz;pozzz=v[i];}					//la fiecare nod din arb partial
		}
	v[++vv]=pozz;
	viz[pozz]=1;
	cost+=mintotal;
	ff[vv-1].x=pozz;
	ff[vv-1].y=pozzz;
	a[pozz][pozzz]=a[pozzz][pozz]=INF;	//stergem legatura din matrice
}

g<<cost<<"\n"<<vv-1<<"\n";
for(i=1;i<=vv-1;i++) g<<ff[i].x<<" "<<ff[i].y<<"\n";
f.close();
g.close();
return 0;
}