#include<fstream>
#include<algorithm>
using namespace std;
#define lim 200001
typedef struct MUC{
	int x,y,c;};
MUC V[lim];
int n,m,S,tata[lim],niv[lim],rez[lim];
int cmp(MUC a,MUC b)
{
	return a.c<b.c;
}
int cautata(int x)
{
	int T,aux;
	T=x;
	while(T!=tata[T])
		T=tata[T];
	while(x!=tata[x])
	{
		aux=tata[x];
		tata[x]=T;
		x=aux;
	}
	return T;
}
void unire(int x,int y)
{
	if(niv[x]>niv[y])
	{
		tata[y]=x;
		niv[y]++;
	}
	else
	{
		tata[x]=y;
		niv[x]++;
	}
	if(niv[x]==niv[y])
	{
		niv[y]++;
		niv[x]++;
	}
}
int main()
{
	int i,j;
	ifstream in("apm.in");
	in>>n>>m;
	for(i=1;i<=m;++i)
		in>>V[i].x>>V[i].y>>V[i].c;
	sort(V+1,V+m+1,cmp);
	for(i=1;i<=n;++i)
	{
		tata[i]=i;
		niv[i]=1;
	}
	j=0;
	for(i=1;i<=m&&j<n-1;++i)
	{
		if(cautata(V[i].x)!=cautata(V[i].y))
		{
			unire(V[i].x,V[i].y);
			S+=V[i].c;
			rez[++j]=i;
		}
	}
	ofstream out("apm.out");
	out<<S<<'\n'<<n-1<<'\n';
	for(i=1;i<n;++i)
		out<<V[rez[i]].x<<" "<<V[rez[i]].y<<'\n';
	return 0;
}