#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, M, sum;
vector <pair<int, pair<int, int>>> m, g;
int reprezentant[200005];

void citire()
{
	int x, y, c;
	fin >> n >> M;
	while (fin >> x >> y >> c)
		m.push_back({ c, {x, y} });
	sort(m.begin(), m.end());
}

int find(int nod)
{
	if (reprezentant[nod] == nod) 
		return nod;
	else
	{
		reprezentant[nod] = find(reprezentant[nod]);
		return reprezentant[nod];
	}
}

void unire(int nod1, int nod2)
{
	reprezentant[nod2] = nod1;
}

void kruskal()
{
	for (int i = 1; i <= n; i++)
		reprezentant[i] = i;

	while (g.size() != n - 1)
	{
		pair<int, pair<int, int>> aux;
		aux = m[0];
		m.erase(m.begin());
		int nod1 = aux.second.first;
		int nod2 = aux.second.second;
		int rep1 = find(nod1);
		int rep2 = find(nod2);
		if (rep1 != rep2)
		{
			unire(rep1, rep2);
			g.push_back(aux);
			sum += aux.first;
		}
	}
}

void afisare()
{
	fout << sum << '\n' << g.size() << '\n';
	for (auto x : g)
		fout << x.second.first << " " << x.second.second;
}

int main()
{
	citire();
	kruskal();
	afisare();
	return 0;
}