#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,i,j,t1,t2,nz,s;

struct mch	{int a, b, c;}	M[400005];
struct nod 	{int f, h;}	arb[200005], rz[200005];

bool cmp (mch &a, mch &b)
{
	return a.c<b.c;
}
int tata(int nod)
{
	if(arb[nod].f==0)	return nod;
	arb[nod].f=tata(arb[nod].f);
	return arb[nod].f;
}

int main() {
	
	fin>>n>>m;
	for(i=1;i<=m;i++)
		fin>>M[i].a>>M[i].b>>M[i].c;
	
	sort(M+1,M+m+1,cmp);
	
	i=0;
	nz=0;
	while(nz<n-1)
	{
		i++;
		t1=tata(M[i].a);
		t2=tata(M[i].b);
		if(t1!=t2)
		{
			s+=M[i].c;
			rz[++nz].f=M[i].a;
			rz[nz].h=M[i].b;
			
			if(arb[t1].h<=arb[t2].h)
			{
				arb[t1].f=t2;
				arb[t2].h=max(arb[t2].h,arb[t1].h+1);
			}
			else 
			{
				arb[t2].f=t1;
				arb[t1].h=max(arb[t1].h,arb[t2].h+1);
			}
		}
	}
	
	fout<<s<<"\n";
	fout<<nz<<"\n";
	for(i=1;i<=nz;i++)
		fout<<rz[i].f<<" "<<rz[i].h<<"\n";
}