#include<iostream>
#include<fstream>
#define INF 1001
using namespace std;

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

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

int main(void){
f>>n>>m;
long x,y,c;
long cost=0;
int 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;
	}

int k=0;
v[1]=1;
viz[1]=1;
int vv=1;
while(vv<n)
{
	int mintotal=INF,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;}
			if(min<mintotal) {mintotal=min;pozz=poz;pozzz=v[i];}
		}
	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;
}

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;
}