// kruskal.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

struct el
{
	long long cs1, cs2, ar;
};
vector<el>x;
vector<long long>y;
vector<pair<int, int>>res;
long long n, m, i;
int has(el a, el b)
{
	if (a.ar < b.ar) return 1;
	return 0;
}
int main()
{
	cin >> n >> m;
	x.resize(m + 1);
	y.resize(n + 1);
	long long db = 0, sum = 0;
	for (i = 1; i <= m; ++i)
	{
		cin >> x[i].cs1 >> x[i].cs2 >> x[i].ar;
	}
	sort(x.begin()+1, x.end(), has);
	//for (i = 1; i <= n; ++i)cout<<x[i].ar << " ";
	for (i = 1; i <= n; ++i)y[i] = i;
	for (i = 1; i <= m; ++i)
	{
		int a = x[i].cs1;
		int b = x[i].cs2;
		int k = x[i].ar;
		if (y[a] != y[b])
		{
			db ++;
			res.push_back({ a,b });
			sum += k;
			int p = y[a], q = y[b];
			for (int j = 1; j <= n; ++j)
				if (y[j] == q)y[j] = p;
			if (db == n - 1)break;

		}
	}
	cout << sum << "\n"<<db<<"\n";
	for (auto& e : res)cout << e.first << " " << e.second << "\n";
	return 0;
	/*9 14
1 2 10
1 3 -11
2 4 11
2 5 11
5 6 13
3 4 10
4 6 12
4 7 5
3 7 4
3 8 5
8 7 5
8 9 4
9 7 3
6 7 11*/
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file