#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];

inline int cmp(lista a, lista b)
{
	return a.z<b.z;
};


void sterge(int val)
{
	int i,ok=0;
	for(i=0;i<mat.size();++i)
		if(val==mat[i])
		{
			ok=1;
			break;
		}
	
		if(ok==1)
			mat.erase (mat.begin()+i);
	
	for(i=0;i<mat.size();++i)
		cout<<mat[i] <<" ";
	cout<<'\n';
}



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;
	
	for(i=0;i<n;++i)
		mat.push_back(i+1);
	
	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;

	sterge(v[1].x);
	sterge(v[1].y);
	
	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];
					sterge(v[i].x);
			}
			else
			if(vizitat[v[i].y]==0)
			{
				vizitat[v[i].y]=vizitat[v[i].x];
				sterge(v[i].y);
			}
			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;
					sterge(j);
				}
				
			}
		}
	}

	
	if( mat.size()==0)
		break;
	
	}
				
	fout<<contor<<'\n';
	fout<<fu <<'\n';
	for(i=0;i<fu;++i)
		fout<<sol[i][0] <<" "<<sol[i][1] <<'\n';
	
	
	return 0;
}