#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define infinit 1234567890
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");
vector< pair <int, int> > myGraph[200003], muchii;
priority_queue < pair <int, pair<int, int> > > myHeap;
int n, m, viz[200003], x, y, c;
int main()
{
	in >> n >> m;

	for (int i = 1; i <= m; i++)
	{
		in >> x >> y >> c;
		myGraph[x].push_back(make_pair(c, y));
		myGraph[y].push_back(make_pair(c, x));
	}

	int costTotal = 0;
	viz[1] = 1;

	for (int i = 0; i < (int)myGraph[1].size(); i++)
	{
		pair<int, int> aux = myGraph[1][i];
		pair<int, pair<int, int> > muchie = make_pair(-aux.first, make_pair(1, aux.second));
		myHeap.push(muchie);
	}

	while (myHeap.empty() == 0)
	{
		pair<int, pair<int, int> > minim = myHeap.top();
		myHeap.pop();
		int index = minim.second.second;

		if (viz[index] == 0)
		{
			viz[index] = 1;
			costTotal += (-1) * minim.first;
			muchii.push_back(minim.second);

			for (int i = 0; i < (int)myGraph[index].size(); i++)
				if (viz[myGraph[index][i].second] == 0)
				{
					pair<int, pair<int, int> > muchie = make_pair(-myGraph[index][i].first, make_pair(index, myGraph[index][i].second));
					myHeap.push(muchie);
				}
		}
	}

	out << costTotal << '\n';
	out << n - 1 << '\n';

	for (int i = 0; i < n - 1; i++)
		out << muchii[i].first << " " << muchii[i].second << '\n';

	return 0;
}