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

using namespace std;

vector <tuple<int, int, int> > muchii;
priority_queue <tuple<int, int, int> > heap;
int tata[200005];
int dist[200005];
int find_father(int x)
{
	if (x == tata[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 N, int M)
{
	int x, y, c, i = 0, cost = 0;
	tuple <int, int, int> tuplu;
	while (i < N - 1)
	{
		tuplu = heap.top();
		heap.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 += c;
			muchii.push_back(make_tuple(c, x, y));
			i++;
			unite(find_father(x), find_father(y));
		}
	}
	return cost;
}
int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	int i, N, M, x, y, c;
	f >> N >> M;
	for (i = 1; i <= N; i++)
	{
		tata[i] = i;
		dist[i] = 1;
	}
	for (i = 1; i <= M; i++)
	{
		f >> x >> y >> c;
		heap.push(make_tuple(-c, x, y));
	}
	g << kruskal(N, M) << "\n";
	int lim = muchii.size();
	g << lim << "\n";
	for (i = 0; i < lim; i++)
		g << get<1>(muchii[i]) << " " << get<2>(muchii[i]) <<"\n";
	return 0;
}
#endif