#include<fstream>
#include<vector>
using namespace std;
#define mpp make_pair
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{	int x,y,cost;
}gr[400001];
bool v[200001];
int mf[100000];
int N,M;
int main()
{	int i,x,y,c,minct,j,k;
	long ct=0;
	f>>N>>M;
	for(i=1;i<=M;i++)
	{	f>>gr[i].x>>gr[i].y>>gr[i].cost;
	}
	v[1]=1;
	for(i=2,k=0;i<=N;i++)
	{	minct=5000000;
		for(j=1;j<=M;j++)
			if((v[gr[j].x] && !v[gr[j].y])||(!v[gr[j].x] && v[gr[j].y]))
				if(minct>gr[j].cost)
					minct=gr[j].cost, c=j;
		mf[++k]=c; v[gr[c].x]=v[gr[c].y]=1; ct+=gr[c].cost;
	}
	g<<ct<<'\n'<<N-1<<'\n';
	for(i=1;i<=k;i++)
		g<<gr[mf[i]].x<<" "<<gr[mf[i]].y<<'\n';
	f.close();
	g.close();
	return 0;
}