#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

#define NMAX 200001
#define MMAX 400001

int n, m;
int x_graph[MMAX], y_graph[MMAX], costs[MMAX], idx[MMAX];
int x_mst[NMAX], y_mst[NMAX];

int trees[NMAX], heights[NMAX];

int get_root(int x)
{
	int root_x, y, aux;

	// get root
	root_x = x;
	while (root_x != trees[root_x])
		root_x = trees[root_x];

	// compress the paths
	y = x;
	while (y != root_x) {
		aux = trees[y];
		trees[y] = root_x;
		y = aux;
	}

	return root_x;
}

void join(int x, int y)
{
	x = get_root(x);
	y = get_root(y);

	// link the smaller tree to the bigger one
	if (heights[x] < heights[y]) {
		trees[x] = y;
		heights[y] = max(heights[y], 1 + heights[x]);
	} else {
		trees[y] = x;
		heights[x] = max(heights[x], 1 + heights[y]);
	}
}

int are_joint(int x, int y)
{
	return get_root(x) == get_root(y);
}

int main()
{
	ifstream fin("apm.in");
	ofstream fout("apm.out");

	// read input
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		fin >> x_graph[i] >> y_graph[i] >> costs[i];
		idx[i] = i;
	}

	// each node is disjoint
	for (int i = 1; i <= n; i++)
		trees[i] = i;

	// sort edges by cost
	sort(idx + 1, idx + m + 1, [](int a, int b) {return costs[a] < costs[b];});	

	// add n - 1 edges if they are disjoint
	int count = 0, sum = 0;
	for (int i = 1; i <= m; i++) {
		if (!are_joint(x_graph[idx[i]], y_graph[idx[i]])) {
			join(x_graph[idx[i]], y_graph[idx[i]]);
			count++;
			x_mst[count] = x_graph[idx[i]];
			y_mst[count] = y_graph[idx[i]];
			sum += costs[idx[i]];

			if (count == n - 1)
				break;
		}
	}

	// print output
	fout << sum << endl << count << endl;
	for (int i = 1; i <= count; i++)
		fout << y_mst[i] << ' ' << x_mst[i] << endl;

	return 0;
}