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

ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<int, pair<int, int>>> muchie;
vector<pair<int, int>>graf;
int tata[200001];
int grad[200001];
int n,m, x, y, c,cost;
int find_tata(int nod)
{
	if (tata[nod] == nod)
        return nod;
	tata[nod] = find_tata(tata[nod]);
	return tata[nod];
}
void APM()
{
	while (!muchie.empty())
	{
		pair<int, pair<int, int>>p;
		p = muchie.back();
		muchie.pop_back();
		pair<int, int>m;
		m = p.second;
		int fx, fy;
		fx = find_tata(m.first);
		fy = find_tata(m.second);
		if (fx != fy)
		{
			if (grad[fx] < grad[fy])
			{
				tata[fx] = fy;
				grad[fy] += fx;
				graf.push_back(make_pair(m.first, m.second));
				cost += p.first;
			}
			else
			{
				tata[fy] = fx;
				grad[fx] += fy;
				graf.push_back(make_pair(m.first, m.second));
				cost += p.first;
			}
		}
	}
}
int main()
{
	fin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		tata[i] = i;
		grad[i] = 1;
	}
	for (int i = 0; i < m; i++)
	{
		fin >> x >> y >> c;
		muchie.push_back(make_pair(c, make_pair(x, y)));
	}
	sort(muchie.rbegin(), muchie.rend());
	APM();
	fout << cost << '\n';
	int l = graf.size();
	fout << l << '\n';
	for (int i = 0; i < l; i++)
		fout << graf[i].first << " " << graf[i].second << '\n';
}