#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;

}