#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define  MaxN 200005
#define INF 2140000000
#define MAX 131072
using namespace std;

char f[MAX];
int pos=0,sign;
FILE *IN,*OUT;
void Read(int &nr)
{
	nr=0,sign=1;
	while(f[pos]>'9'||f[pos]<'0')
	{
		if(f[pos]=='-')
			sign=-1;
		pos++;
		if(pos==MAX)
			pos=0,fread(f,1,MAX,IN);
	}
	while(f[pos]<='9'&&f[pos]>='0')
	{
		nr=nr*10+f[pos++]-'0';
		if(pos==MAX)
			pos=0,fread(f,1,MAX,IN);
	}
	nr*=sign;
}

int v[MaxN],N,M,X,Y,cost;
struct Edge
{
	int x,y,cost;
}E[2*MaxN],O[MaxN];
void Unite(int x,int y)
{
	if(x!=y)v[y]=x;
}
int Find(int x)
{
	int y=x,aux;
	while(y!=v[y])
		y=v[y];
	while(x!=v[y])
	{
		aux=v[x];
		v[x]=v[y];
		x=aux;
	}
	return y;
}
bool cond(Edge a,Edge b)
{
	return a.cost<b.cost;
}
int main()
{
    IN=fopen("apm.in","r");
    OUT=fopen("apm.out","w");
	fread(f,1,MAX,IN);
	
	Read(N),Read(M);
	for(int i=1;i<=N;i++)
		v[i]=i;
	for(int i=1;i<=M;i++)
		Read(E[i].x),Read(E[i].y),Read(E[i].cost);
	sort(E+1,E+1+M,cond);
	int comp=0;
	int P=1;
	while(comp<N-1)
	{
		X=Find(E[P].x);
		Y=Find(E[P].y);
		if(X!=Y)
		{
			Unite(X,Y);
			cost+=E[P].cost;
			O[++comp]=E[P];
		}
		P++;
	}
	fprintf(OUT,"%d\n%d\n",cost,N-1);
	for(int i=1;i<N;i++)
		fprintf(OUT,"%d %d\n",O[i].x,O[i].y);
	return 0;
}