#include<stdio.h>
#include<malloc.h>
using namespace std;

typedef struct 
{
	long int x;
	long int y;
	int cost;
} xy;

typedef struct _nod
{
	int info;
	struct _nod *adr;
} nod;

typedef struct
{
	struct _nod *cap;
} list;

xy M[200001];
list A[200001];
long int n;
long int m;
long int L[400001];
char T[400001];
long long S;

void citire(void)
{
	FILE *f = fopen("apm.in","r");
	
	fscanf(f,"%d %d",&n,&m);
	for(int i=1;i<=m;i++)
		fscanf(f,"%d %d %d",&M[i].x,&M[i].y,&M[i].cost);
	
	fclose(f);
}

long int poz(int li,int ls)
{
	int i1 = 0;
	int j1 = -1;
	int jiaux = 0;
	xy c = M[(int)(li+ls)/2];
	M[(int)(li+ls)/2] = M[li];
	M[li] = c;
	while(li<ls)
	{
		if(M[li].cost>M[ls].cost) //|| (M[li].cost == M[ls].cost && M[li].cost*M[li].val <M[ls].cost*M[ls].val))
		{
			c = M[li];
			M[li] = M[ls];
			M[ls] = c;
			jiaux = -i1;
			i1 = - j1;
			j1 = jiaux;
		}
		li += i1;
		ls += j1;
	}
	return li;
}

void quick(int li,int ls)
{
	if(li<ls)
	{
	long int k = poz(li,ls);
	quick(li,k-1);
	quick(k+1,ls);
	}
}

void add(int a,int b)
{
	nod *nou = (nod*)malloc(sizeof(nod));
	nou->info = b;
	nou->adr = A[a].cap;
	A[a].cap = nou;
}

void complet(void)
{
	for(int i=1;i<=m;i++)
		L[i] = i;
}

void parcurgere(int i)
{
	int C[200001];
	char viz[200001];
	long int pi = 1;
	long int pf = 1;
	C[1] = i;
	viz[i] = 1;
	while(pi<=pf)
	{
		nod *q = A[C[pi]].cap;
		while(q)
		{
			if(viz[q->info] != 1)
			{
				C[++pf] = q->info;
				L[q->info] = L[i];
			}
			q = q->adr;
		}
		pi ++;
	}
}

void kruscal(void)
{
	long int nr = 0;
	long int k = 1;
	long int pz = 0;
	while(nr < n-1)
	{
		if(L[M[k].x] != L[M[k].y])
		{
			add(M[k].x,M[k].y);
			add(M[k].y,M[k].x);
			S+=M[k].cost;
			T[k] = 1;
			parcurgere(M[k].x);
			nr ++;
		}
		k++;
	}
}

void afisare(void)
{
	FILE *f = fopen("apm.out","w");
	
	fprintf(f,"%lld\n",S);
	fprintf(f,"%d\n",n-1);
	for(int i=1;i<=m;i++)
		if(T[i] == 1)
			fprintf(f,"%d %d\n",M[i].x,M[i].y);
	
	fclose(f);
}

int main()
{
	citire();
	quick(1,m);
	complet();
	kruscal();
	afisare();
	return 0;
}