#include <algorithm>
#include <bitset>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

struct Muchie
{
	int start, end, cost;
};

bool cmp(const Muchie &a, const Muchie &b)
{
	return (a.cost < b.cost);
}

int main()
{
	ifstream in("apm.in");
	
	int N, M;
	in >> N >> M;

	bitset<400001> s(false);
	vector<Muchie> v(M + 1);
	vector<int> t(N + 1, -1);

	for (int i = 1; i <= M; i++)
		in >> v[i].start >> v[i].end >> v[i].cost;

	sort(v.begin() + 1, v.end(), cmp);

	int costMinim = 0;

	queue<int> a;

	for (int i = 1, k = 0; k < (N - 1); i++)
	{
		int start = v[i].start;
		int end = v[i].end;

		while (t[start] > 0)
			start = t[start];

		while (t[end] > 0)
			end = t[end];

		if (start != end)
		{
			if (start < end)
			{
				t[start] += t[end];
				t[end] = start;
			}
			else
			{
				t[end] += t[start];
				t[start] = end;
			}

			k++;

			s[i] = true;
			a.push(i);

			costMinim += v[i].cost;
		}
	}
	
	ofstream out("apm.out");
	out << costMinim << '\n' << (N - 1) << '\n';

	for (; !a.empty(); a.pop())
		out << v[a.front()].start << ' ' << v[a.front()].end << '\n';
}