#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream in ("apm.in");
ofstream out ("apm.out");
set <pair <int, pair <int, int> > > seti;
int tata[200001], rang[200001];
int cost = 0;
vector <pair <int, int> > ans;
int find_tata(int nod)
{
	int cop = nod;
	while (tata[nod] != nod)
		nod = tata[nod];
	while (cop != nod)
	{
		int t = tata[cop];
		tata[cop] = nod;
		cop = t;
	}
	return nod;
}
void unite (int x, int y)
{
	if (rang[x] > rang[y])
		tata[y] = x;
	else 
	{
		tata[x] = y;
		if (rang[x] == rang[y])
			rang[x]++;
	}
}
void apm ()
{
	while (!seti.empty())
	{
		int x = (*seti.begin()).second.first;
		int y = (*seti.begin()).second.second;
		int c = (*seti.begin()).first;
		seti.erase(seti.begin());
		int tatax = find_tata(x);
		int tatay = find_tata(y);
		if (tatax != tatay)
		{
			unite(tatax, tatay);
			cost += c;
			ans.push_back({x, y});
		}
 	}
}
main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1;i<=m;++i)
	{
		int a, b, c;
		cin >> a >> b >> c;
		seti.insert({c, {a, b}});
		seti.insert({c, {b, a}});
	}
	for (int i = 1;i<=n;++i)
		tata[i] = i;
	apm();
	cout << cost << '\n';
	cout << ans.size() << '\n';
	for (auto it:ans)
		cout << it.first << ' ' << it.second << '\n';
	return 0;
}