#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
const int nmax = 200000;
const int mmax = 400000;
int n, m;
int t[nmax + 1];
int rang[nmax + 1];
struct muchie{
	int x, y, c;
};
bool comp(const muchie& a,const muchie& b)
{
	return a.c < b.c;
}
vector<muchie>d(mmax+1);
vector<pair<int, int>>sol;
int radacina(int k)
{
	if (t[k]==k)
		return k;
	else
	{
		int x = radacina(t[k]);
		t[k] = x;
		return x;
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		t[i] = i;
	for (int i = 0; i < m; i++)
	{
		int x, y, c;
		cin >> x >> y >> c;
		d[i].x = x;
		d[i].y = y;
		d[i].c = c;
	}
	sort(d.begin(), d.begin() + m, comp);
	int costTot = 0;
	for (int i = 0; i < m; i++)
	{
		int rk = radacina(d[i].x);
		int rp = radacina(d[i].y);
		if (rp != rk)
		{
			if (rang[rp] > rang[rk])
				t[rk] = rp;
			else
			{
				t[rp] = rk;
				if (rang[rp] == rang[rk])
					rang[rk]++;
			}
			costTot += d[i].c;
			sol.push_back({ d[i].x,d[i].y });
		}
	}
	cout << costTot << '\n' << n-1 << '\n';
	for (auto x : sol)
		cout << x.first << ' ' << x.second << '\n';
	return 0;
}