#include <iostream>
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int gr[500000], node_x[500000], node_y[500000], value[500000];
int n, m, totalcost=0, index[500000];
vector<int>v;

int group(int i)
{
	if (gr[i] == i)
		return i;
	gr[i] = group(gr[i]);
	return gr[i];
}

void reunion(int i, int j)
{
	gr[group(i)] = group(j);
}

bool comparation(int i, int j)
{
	return (value[i] < value[j]);
}

int main()
{
	ifstream f;
	f.open("apm.in");
	f >> n >> m;

	for (int i = 1; i <= m; ++i)
	{
		f >> node_x[i] >> node_y[i] >> value[i];
		index[i] = i;
	}

	f.close();

	for (int i = 1; i <= n; ++i)
	{
		gr[i] = i;
	}

	sort(index + 1, index + m + 1, comparation);

	for (int i = 1; i <= m; ++i)
	{
		if (group(node_x[index[i]]) != group(node_y[index[i]]))
		{
			totalcost = totalcost + value[index[i]];
			reunion(node_x[index[i]], node_y[index[i]]);
			v.push_back(index[i]);
		}
	}

	ofstream g;
	g.open("apm.out");
	g << totalcost << '\n' << n - 1 << '\n';
	for (int i = 0; i < n - 1; i++)
		g << node_x[v[i]] << ' ' << node_y[v[i]] << '\n';
	g.close();
    return 0;
}