//#include<iostream>
//#include <stdio.h>
#include<fstream>
#include<algorithm>
#define MX 200001
using namespace std;
long cc[MX],G[MX*2],N,M,H[MX*2];
struct muchie{long x,y;int c;}A[MX*2];

int comp(long a,long b)
{
	if(A[a].c>A[b].c)return 1;//"a" e inaintea lui "b" return 1
	return 0;
}

void read()
{
	ifstream f ("apm.in");
	f>>N>>M;
	for(long i=1;i<=M;i++)
	{
		f>>A[i].x>>A[i].y>>A[i].c;
		H[i]=i;
	}
	f.close();
	for(long i=1;i<=N;i++) cc[i]=i;
	make_heap(H+1,H+M+1,comp);
	//sort_heap(H+1,H+M+1,comp);
}

int main()
{
	read();
	//for(long i=1;i<=M;i++)
	//	cout<<A[H[i]].x<<' '<<A[H[i]].y<<' '<<A[H[i]].c<<'\n';
	
	long Mi,Ma,L=0,Smin=0;
	while(L<=N-1)
	{
		if(cc[A[H[1]].x]!=cc[A[H[1]].y])
		{
			G[++L]=H[1];
			Smin+=A[H[1]].c;
			Mi=min(cc[A[H[1]].x],cc[A[H[1]].y]);
			Ma=max(cc[A[H[1]].x],cc[A[H[1]].y]);
			replace(cc+1,cc+N+1,Ma,Mi);
		}
		pop_heap(H+1,H+M+1,comp);M--;
	}
	
	//ofstream g("apm.out");
	//g<<Smin<<'\n'<<L<<'\n';
	//for(long i=1;i<=L;i++)
	//	g<<A[G[i]].y<<' '<<A[G[i]].x<<'\n';
	//g.close();
	
	FILE *g;
	g = fopen("apm.out","w");
	fprintf(g,"%d\n%d\n",Smin,L);
	for(long i=1;i<=L;i++) fprintf(g,"%d %d\n",A[G[i]].y,A[G[i]].x);
	fclose(g);
	return 0;
}