#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int MAXN = 200010;

int n, m, x, y, c, cost, radA, radB, tata[MAXN], size[MAXN];
pair<int, pair<int, int> > arb[2*MAXN];
vector<pair<int, int> > res;

void read()
{
	f >> n >> m;
	for(int i = 1; i <= m; ++i)
		f >> x >> y >> c, arb[i] = make_pair(c, make_pair(x, y));
}

int find(int a)
{
	int b, p;
	for(p = a; p != tata[p]; p = tata[p]);
	while(a != p)
	{
		b = tata[a];
		tata[a] = p;
		a = b;
	}
	return p;
}

void merge(int a, int b)
{
	if(size[a] >= size[b])
		size[a] += size[b], tata[b] = a;
	else
		size[b] += size[a], tata[a] = b;
}

void kruskal()
{
	cost = 0;
	
	for(int i = 1; i <= m; ++i)
	{
		x = arb[i].second.first; y = arb[i].second.second; c = arb[i].first;
		radA = find(x);
		radB = find(y);
		if(radA != radB)
		{
			cost += c;
			merge(radA, radB);
			res.push_back(make_pair(x, y));
		}
	}
	
	g << cost << '\n' << res.size() << '\n';
	for(int i = 0; i < (int) res.size(); ++i)
		g << res[i].first << " " << res[i].second << '\n';
}

int main()
{
	read();
	sort(arb + 1, arb + m + 1);
	for(int i = 1; i <= n; ++i)
		tata[i] = i, size[i] = 1;
	kruskal();
}