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

int sef[100010];
int marime[100010];
vector <int> adia[100010];
vector <pair <int, pair <int, int>>> muchii;

int cost_total;
int gaseste(int nod);
void uneste(int a, int b);
bool comp_dif(int a, int b);

int main()
{
	ifstream in("apm.in");
	int n, m, a, b, c;
	in >> n >> m;

	for (int i = 1; i <= n; i++)
		sef[i] = i, marime[i] = 1;

	while (m--) {
		in >> a >> b >> c;
		muchii.push_back({ c, { a, b } });
	}

	sort(muchii.begin(), muchii.end());

	for (auto i : muchii) {
		if (comp_dif(i.second.first, i.second.second)) {
			uneste(i.second.first, i.second.second);
			cost_total += i.first;
			adia[i.second.first].push_back(i.second.second);
		}
	}

	/// am creat listele de adiacenta :)

	ofstream out("apm.out");

	out << cost_total << '\n' << n - 1 << '\n';
	for (int i = 1; i <= n; i++)
		for (auto j : adia[i])
			out << i << ' ' << j << '\n';
	in.close();
	out.close();
	return 0;
}



bool comp_dif(int a, int b)
{
	a = gaseste(a);
	b = gaseste(b);
	return (!(a == b));
}

void uneste(int a, int b)
{
	a = gaseste(a);
	b = gaseste(b);
	if (marime[a] > marime[b]) {
		sef[b] = a;
		marime[a] += marime[b];
	}
	else {
		sef[a] = b;
		marime[b] += marime[a];
	}
}

int gaseste(int nod)
{
	if (sef[nod] == nod)
		return nod;
	sef[nod] = gaseste(sef[nod]);
	return sef[nod];
}