#include <stdio.h>
#include <stdlib.h>

#define M 400000
#define N 200000

int n, m;
struct muchie
{
	int x, y, c;
};

muchie v[M];
int rez[N - 1];

int t[N + 1];
int cost = 0;

void citeste()
{
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; ++i)
		scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].c);
}

int fcmp(const void * a, const void * b)
{
	return ((muchie*)a) -> c - ((muchie*)b) -> c;
}

void init()
{
	for(int i = 1; i <= n; ++i) t[i] = i;
}

void reuneste(int a, int b)
{
	t[a] = b;
}

int reprezentant(int a)
{
	while(t[a] != a) a = t[a];
	return a;
}

void kruskal()
{
	int i, k = 0, r1, r2;
	for(i = 0; i < n - 1; ++i)
	{
		while((r1 = reprezentant(v[k].x)) == (r2 = reprezentant(v[k].y))) k++;
		rez[i] = k;
		cost += v[k].c;
		reuneste(r1, r2);
	}
}

void scrie()
{
	printf("%d\n", cost);
	printf("%d\n", n - 1);
	for(int i = 0; i < n - 1; ++i) printf("%d %d\n", v[rez[i]].x, v[rez[i]].y);
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	citeste();
	init();
	qsort(v, m, sizeof(muchie), fcmp);
	kruskal();
	scrie();
	return 0;
}