#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
///-------FISIERE-------
ifstream in("apm.in");
ofstream out("apm.out");

int grad[200003], tata[200003];

int findFather(int x)
{
	if (tata[x] == x)
		return x;
	else return findFather(tata[x]);
}

vector < pair<int, int> > arbore;
priority_queue < pair < int, pair <int, int> > > myHeap;


int main()
{
    int n, m, c, cost, nrMuchii;
	in >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		tata[i] = i;
		grad[i] = 1;
	}

	for (int i = 1; i <= m; i++)
	{
		int x, y;
		in >> x >> y >> c;
		myHeap.push(make_pair((-1)* c, make_pair(x, y)));
	}

	cost = 0;
	nrMuchii = 0;

	while (myHeap.empty() == 0 && nrMuchii < m - 1)
	{
		pair <int, pair<int, int> > Min = myHeap.top();
		myHeap.pop();
		int x = Min.second.first;
		int y = Min.second.second;
		int f1 = findFather(x);
		int f2 = findFather(y);

		if (f1 != f2)
		{
		    cost = cost + (-1) * Min.first;
			nrMuchii++;
			if (grad[f1] < grad[f2])
			{
				tata[f1] = f2;
				grad[f2] += grad[f1];
			}
			else
			{
				tata[f2] = f1;
				grad[f1] += grad[f2];
			}

			arbore.push_back(make_pair(x,y));
		}
	}

	out << cost << '\n';
	out << nrMuchii << '\n';
	for(int i = 0; i < nrMuchii; i++)
        out << arbore[i].first << " " << arbore[i].second << '\n';

	return 0;
}