#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

struct Edge {
	int t, h, c;
};
bool operator< (const Edge &a, const Edge &b)
{ return a.c < b.c; }

int find_set (int x, vector <int> &ds)
{
	int rep = x;
	while (rep != ds[rep]) rep = ds[rep];
	while (x != ds[x])
	{
		int t = x;
		x = ds[t];
		ds[t] = rep;
	}
	return rep;
}

void union_set (const Edge &e, vector <int> &ds, vector <int> &rs)
{
	int x = find_set (e.t, ds),
		y = find_set (e.h, ds);
	if (rs[x] > rs[y])
		ds[y] = x;
	else
	{
		ds[x] = y;
		if (rs[x] == rs[y])
			rs[y]++;
	}
}

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

	int N, M;
	fin >> N >> M;

	vector <Edge> edges (M);
	for (int i = 0; i < M; ++i)
		fin >> edges[i].t >> edges[i].h >> edges[i].c;
	sort (edges.begin(), edges.end());

	vector <int> disjoint_set (N+1, 0), rank_set (N+1, 0);
	for (int v = 1; v <= N; ++v) disjoint_set[v] = v;

	int apm_cost = 0;
	vector <Edge> sol;
	for (auto &edge : edges)
		if (find_set (edge.t, disjoint_set) != find_set (edge.h, disjoint_set))
		{
			union_set (edge, disjoint_set, rank_set);
			apm_cost += edge.c;
			sol.push_back (edge);
		}

	fout << apm_cost << '\n' << sol.size() << '\n';
	for (auto &edge : sol)
		fout << edge.t << ' ' << edge.h << '\n';

	fout.close();
	return EXIT_SUCCESS;
}