#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, cost, cnt;
int tati[100005];
struct muchie{
	int x, y, c;
};
int a[100005], b[100005];
muchie v[100005];
bool comp(muchie a, muchie b)
{
	return a.c < b.c;
}
void Union(int x, int y)
{
	tati[y] = x;
}
int Find(int x)
{
	int rad, y;
	rad = x;
	while (tati[rad])
		rad = tati[rad];
	while (tati[x])
		y = tati[x], tati[x] = rad, x = y;
	return rad;
}
int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		int x, y, c;
		fin >> x >> y >> c;
		v[i] = {x, y, c};
	}
	sort(v + 1, v + m + 1, comp);
	for (int i = 1; i <= m; ++i)
	{
		int x, y;
		x = v[i].x,  y = v[i].y;
		x = Find(x);
		y = Find(y);
		if (x != y)
		{
			Union(x, y);
			cost += v[i].c;
			++cnt;
			a[cnt] = v[i].x;
			b[cnt] = v[i].y;
		}
	}
	fout << cost << "\n" << cnt << "\n";
	for (int i = 1; i <= cnt; ++i)
		fout << a[i] << " " << b[i] << "\n";
	return 0;
}