#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define x first
#define y second
#define pip pair<int, pair<int, int> >

const int MAX_N = 200010;
const int MAX_M = 400010;

int n, m, k, sol;
int p[MAX_N], f[MAX_M];
pip a[MAX_M];

int find_dad(int nod)
{
	if (nod == p[nod])
		return nod;
	return p[nod] = find_dad(p[nod]);
}

inline void unite(int t1, int t2)
{
	if (rand() % 2)
		p[t1] = t2;
	else
		p[t2] = t1;
}

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

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

	for (i = 1; i <= m; ++i)
		scanf("%d %d %d", &a[i].y.x, &a[i].y.y, &a[i].x);

	sort(a + 1, a + m + 1);

	for (i = 1; i <= n; ++i)
		p[i] = i;

	for (i = 1; i <= m; ++i)
	{
		int t1 = find_dad(a[i].y.x), t2 = find_dad(a[i].y.y);

		if (t1 != t2)
		{
			f[i] = 1;
			++k;
			sol += a[i].x;

			unite(t1, t2);
		}
	}

	printf("%d\n%d\n", sol, k);

	for (i = 1; i <= m; ++i)
		if (f[i])
			printf("%d %d\n", a[i].y.x, a[i].y.y);
}