#include<fstream>
#include<algorithm>
#define MAX 400001
#define NMAX 200001
using namespace std;
int N,M,T[NMAX],R[NMAX];
struct muchie
{
	int x,y,c,a;
}V[MAX];
int cmp(muchie a, muchie b)
{
	return (a.c<b.c);
}
void read()
{
	ifstream f("apm.in");
	f>>N>>M;
	int i;
	for(i=1;i<=M;++i)
	{
		if(i<=N)
		{
			T[i] = i;
			R[i] = 1;
		}
		f>>V[i].x>>V[i].y>>V[i].c;
	}
	f.close();
}
void compress(int x, int father)
{
	int aux;
	while(T[x]!=x)
	{
		aux = T[x];
		T[x] = father;
		x = aux;
	}
}
void unite(int x,int y)
{
	if(R[x] >= R[y])
	{
		R[x]+=R[y];
		T[y] = x;
	}
	else
	{
		R[y]+=R[x];
		T[x] = y;
	}
}
int find(int x)
{
	int init = x;
	while(T[x]!=x)
		x = T[x];
	compress(init, x);
	return x;
}
int main()
{
	read();
	sort(V+1, V+M+1, cmp);
	int i,cnt = 1,last = 1,s = 0;
	while(cnt<N)
	{
		for(i=last;i<=M;++i)
		{
			if(find(V[i].x)!=find(V[i].y))
			{
				V[i].a = 1;
				s+=V[i].c;
				unite(T[V[i].x], T[V[i].y]);
				last = i+1;
				i=M+1;
			}
		}
		++cnt;
	}
	ofstream g("apm.out");
	g<<s<<"\n"<<N-1<<"\n";
	for(i=1;i<=M;++i)
		if(V[i].a)g<<V[i].x<<" "<<V[i].y<<"\n";
	g.close();
	return 0;
}