#include <iostream>
#include <fstream>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie {
	int x, y, cost;
	bool select;
};
muchie v[400005],aux;
int n, m, t[200005],cate_select;
long long cost;

int main()
{
	f >> n >> m;
	for (int i = 1; i <= m; i++)
		f >> v[i].x >> v[i].y >> v[i].cost;
	for (int i = 1; i <= n; i++)
		t[i] = i;
	for(int i=1;i<=m;i++)
		for(int j=i+1;j<=m;j++)
			if (v[i].cost > v[j].cost)
			{
				aux = v[i];
				v[i] = v[j];
				v[j] = aux;
			}
	for(int i=1;i<=m;i++)
		if (t[v[i].x] != t[v[i].y])
		{
			v[i].select = 1;
			cate_select++;
			cost += v[i].cost;
			int a = t[v[i].x];
			int b = t[v[i].y];
			for (int i = 1; i <= n; i++)
				if (t[i] == b)
					t[i] = a;
		}
	g << cost << '\n' << cate_select << '\n';
	for (int i = 1; i <= m; i++)
		if (v[i].select)
			g << v[i].x << " " << v[i].y << '\n';
	return 0;
}