#include <bits/stdc++.h>
 
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct vrajeala
{
	int x, y, cost, ales;
	bool operator < (const vrajeala A) const
	{
		return cost < A.cost;
	}
}a[200005];

int n, m, sol, t[200005];

int Find(int x)
{
	int r = x, y;

	while (t[r] != 0)
		r = t[r];

	while (r != x)
	{
		y = t[x];
		t[x] = r;
		x = y;
	}

	return x;
}

void Union(int x, int y)
{
	t[y] = x;
}

int main()
{
	int i, x, y, cost, nrcc;
	fin >> n >> m;
	nrcc = n;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> cost;
		a[i] = { x, y, cost, 0 };
	}

	sort(a + 1, a + m + 1);
	for (i = 1; i <= m and nrcc > 1; i++)
	{
		x = Find(a[i].x);
		y = Find(a[i].y);
		if (x != y)
		{
			Union(x, y);
			a[i].ales = 1;
			sol += a[i].cost;
			nrcc--;
		}
	}
	fout << sol << "\n" << n - 1 << "\n";
	for (i = 1; i <= m; i++)
		if (a[i].ales == 1)
			fout << a[i].x << " " << a[i].y << "\n";

	return 0;
}