#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct vectoR {
	int x, y, cost;
};
int n, m;
int cnt = 0;
vectoR v[400001];
int rang[200001],i,j, t[200001], k;
pair<int, int>afisare[200001];
int crit(vectoR a, vectoR b)
{
	return(a.cost < b.cost);
}
void marcare_tata(int* v)
{
	for ( i = 1; i <= n; i++)
		v[i] = i, rang[i] = 1;
}
void uneste(int x, int y)
{

	if (rang[y] < rang[x])
		t[y] = x;
	else
	{
		t[x] = y;
		if (rang[x] == rang[y])
			rang[y]++;
	}
}
int answer = 0;
int radacina(int nod)
{
	if (t[nod] != nod)
		t[nod] = radacina(t[nod]);
	return t[nod];
}
void kruskal()
{
	int a, b;
	for ( i = 1; i <= m && cnt < n; i++)
	{
		a = radacina(v[i].x);
		b = radacina(v[i].y);
		if (a != b)
		{
			afisare[++k].first = v[i].x;
			afisare[k].second = v[i].y;
			answer += v[i].cost;
			cnt++;
			uneste(b, a);
		}
	}
}
int main() {
	f >> n >> m;
	for ( i = 1; i <= m; i++)
	{
		f >> v[i].x >> v[i].y >> v[i].cost;
	}
	marcare_tata(t);

	sort(v + 1, v + m + 1, crit);
	kruskal();
	g << answer << "\n";
	g << k << "\n";
	for ( i = 1; i <= k; i++)
		g << afisare[i].first << " " << afisare[i].second << endl;
}