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

using namespace std;

int tata[500001];
int dist[50001];
priority_queue<tuple<int, int, int>>myheap;
vector<tuple<int, int, int>>muchii;
int find_father(int x)
{
	if (tata[x] == x)
		return x;
	return find_father(tata[x]);
}
void unite(int x, int y)
{
	if (dist[x] > dist[y])
		tata[y] = tata[x];
	else {
		tata[x] = tata[y];}
	if (dist[x] == dist[y])
		dist[y]++;
}
int kruskal(int noduri)
{
	int x, y, c, cost = 0, i = 0;
	tuple<int, int, int>tuplu;
	while (i < noduri - 1)
	{
		tuplu = myheap.top();
		myheap.pop();
		get<0>(tuplu) = -get<0>(tuplu);
		x = get<1>(tuplu);
		y = get<2>(tuplu);
		c = get<0>(tuplu);
		if (find_father(x) != find_father(y))
		{
			cost = cost + c;
			muchii.push_back(make_tuple(c, x, y));
			i++;
			unite(find_father(x), find_father(y));
		}
	}
	return cost;
}
int main()
{
	int noduri, M, x, y, c;
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	fin >> noduri;
	fin >> M;
	for (int i = 1; i <= noduri; i++)
	{
		dist[i] = 1;
		tata[i] = i;
	}
	for (int i = 1; i <= M; i++)
	{
		fin >> x >> y >> c;
		myheap.push(make_tuple(c, x, y));
	}
	fout << kruskal(noduri)<<"\n";
	int lim = muchii.size();
	fout << lim << "\n";
	for (int i = 0; i < lim; i++)
		fout << get<1>(muchii[i]) << " " << get<2>(muchii[i]);
	return 0;
}