#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 200001
#define EMAX 400001

typedef struct edge {
	int x, y, cost;
} EDGE;

int n, m, i, j, k, c;
int t[NMAX], h[NMAX];
vector<EDGE> e;
vector<EDGE> res;
int result;

void Union(int a, int b);
int Find(int a);
int Compare(EDGE e1, EDGE e2) { return e1.cost < e2.cost; }

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (k = 0; k < m; k++)
	{
		scanf("%d %d %d", &i, &j, &c);
		EDGE ed;
		ed.x = i;
		ed.y = j;
		ed.cost = c;
		e.push_back(ed);
	}

	sort(e.begin(), e.end(), Compare);

	for (k = 1; k <= n; h[k] = 1, t[k] = k, k++);

	for (k = 0; k < m; k++)
	{
		i = Find(e[k].x);
		j = Find(e[k].y);
		if (i != j)
		{
			Union(i, j);
			result += e[k].cost;
			res.push_back(e[k]);
		}
	}

	printf("%d\n%d\n", result, n-1);
	for (vector<EDGE>::iterator it = res.begin(); it != res.end(); it++)
		printf("%d %d\n", (*it).x, (*it).y);

	return 0;
}

int Find(int a)
{
	if (a == t[a]) return a;
	else return (t[a] = Find(t[a]));
}

void Union(int a, int b)
{
	if (h[a] > h[b])
	{
		t[b] = a;
	}
	else
	{
		t[a] = b;
		if (h[a] == h[b]) h[b]++;
	}
}