#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;
#define dim	400005
ifstream fin("apm.in");
ofstream fout("apm.out");
struct lista
{
	int x, y, z;
}v[dim];
typedef struct{int x,y;}lista1;
	
int vizitat[dim], parinte[dim], grad[dim];
lista1 sol[dim];
struct cmp{
	bool operator()(const lista &a,const lista &b)const
	{
		if(a.z<b.z)
			return 1;
		return 0;
	}
};

int main()
{
	int i,n,m;
	fin>>n >>m;
	
	for(i=1;i<=m;++i)
	{
		fin>>v[i].x >>v[i].y >>v[i].z;
		parinte[i]=i;
		grad[i]=i;
	}
	
	sort(v+1,v+m+1,cmp());
	
	int aux1, aux2,muchie=0,cost=0;
	
	for(i=1;i<=m && muchie<=n-1;++i)
	{
		aux1=v[i].x;
		aux2=v[i].y;
		while(aux1!=parinte[aux1])
			aux1=parinte[aux1];
		while(aux2!=parinte[aux2])
			aux2=parinte[aux2];
		
		if(aux1!=aux2)
		{
			++muchie;
			sol[muchie].x=v[i].x;
			sol[muchie].y=v[i].y;
			cost+=v[i].z;
			if(grad[aux1]<grad[aux2])
				parinte[aux1]=aux2;
			else
				if(grad[aux1]>grad[aux2])
					parinte[aux2]=aux1;
				else
				{
					++grad[aux1];
					parinte[aux2]=aux1;
				}
		}
	}
				
	fout<<cost<<'\n';
	fout<<muchie <<'\n';
	for(i=1;i<=muchie;++i)
		fout<<sol[i].x <<" "<<sol[i].y <<'\n';
	
	
	return 0;
}