#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>>> muchii;
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 formare()
{
	while (!muchii.empty())
	{
		pair<int, pair<int, int>>p;
		p = muchii.back();
		muchii.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;
		muchii.push_back(make_pair(c, make_pair(x, y)));
	}
	sort(muchii.rbegin(), muchii.rend());
	/*for (int i = 0; i < muchii.size(); i++)
	{
		fout << muchii[i].first << " " << muchii[i].second.first<<" "<<muchii[i].second.second<<'\n';
	}*/
	formare();
	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';
	system("pause");
}