#include <fstream>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define dim	400005
ifstream fin("apm.in");
ofstream fout("apm.out");
vector <int > mat;
struct lista
{
	int x, y, z;
}v[dim];
int vizitat[dim],sol[dim][2];

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;
	
	sort(v+1,v+m+1,cmp());
	int contor=0,conex=1,fu=0;
	
	vizitat[v[1].x]=1;
	vizitat[v[1].y]=1;
	
	sol[fu][0]=v[1].x;
	sol[fu++][1]=v[1].y;
	contor+=v[1].z;
	int aux=n-2;
	for(i=2;i<=m;++i)
	{
	
	if( vizitat[v[i].x]==vizitat[v[i].y] && vizitat[v[i].y]==0)
	{
		++conex;
		contor+=v[i].z;
		sol[fu][0]=v[i].x;
		sol[fu++][1]=v[i].y;
		vizitat[v[i].x]=vizitat[v[i].y]=conex;
	}
	else
	{	
		
		if(vizitat[v[i].x]!=vizitat[v[i].y])
		{
			contor+=v[i].z;
			
			sol[fu][0]=v[i].x;
			sol[fu++][1]=v[i].y;
			
			if(vizitat[v[i].x]==0)
				vizitat[v[i].x]=vizitat[v[i].y];
			else
			if(vizitat[v[i].y]==0)
				vizitat[v[i].y]=vizitat[v[i].x];
			
			else
			{
		
			int maxim=0,re;
			re=min(vizitat[v[i].x],vizitat[v[i].y]);
			if(re==vizitat[v[i].x])
				maxim=vizitat[v[i].y];
			else
				maxim=vizitat[v[i].x];
			
			for(int j=1;j<=n;++j)
				if(vizitat[j]==maxim)
					vizitat[j]=re;
				
				
			}
		}
	}
	}
				
	fout<<contor<<'\n';
	fout<<fu <<'\n';
	for(i=0;i<fu;++i)
		fout<<sol[i][0] <<" "<<sol[i][1] <<'\n';
	
	
	return 0;
}