#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n, m, c, grad[200003], tata[200003], costTotal, nrMuchii;

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()
{
	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)));
	}

	int costTotal = 0;
	int nrMuchii = 0;

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

		if (fx != fy)
		{
			if (grad[fx] < grad[fy])
			{
				tata[fx] = fy;
				grad[fy] += grad[fx];
			}
			else
			{
				tata[fy] = fx;
				grad[fx] += grad[fy];
			}

			costTotal += (-1) * minim.first;
			nrMuchii++;
			arbore.push_back(make_pair(x,y));
		}
	}

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

	return 0;
}