#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
using namespace std;

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

int N, M;

struct edge { int x, y, c; };
vector<edge> E;
map<int, int> state, father;

int total = 0;
vector<pair<int, int>> sol;

int GetRoot(int root)
{
	while (root != father[root])
		root = father[root];
	return root;
}

void Unite(int x, int y)
{
	if (state[x] > state[y])
		father[y] = x;
	else
		father[x] = y;

	if (state[x] == state[y])
		father[y]++;
}

inline bool cmp(edge a, edge b)
{
	return a.c < b.c;
}

void Kruskal()
{
	for (int i = 0; i < M; i++)
	{
		int rootX = GetRoot(E[i].x);
		int rootY = GetRoot(E[i].y);
		if (rootX != rootY)
		{
			Unite(rootX, rootY);

			total += E[i].c;
			sol.push_back({ E[i].x, E[i].y });
		}
	}
}

int main()
{
	fin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int x, y, c;
		fin >> x >> y >> c;
		E.push_back({ x, y, c });
	}

	for (int i = 1; i <= N; i++)
		state[i] = father[i] = i;

	sort(E.begin(), E.end(), cmp);
	Kruskal();

	fout << total << "\n";
	fout << sol.size() << "\n";
	for (auto s : sol)
		fout << s.first << " " << s.second << "\n";

	return 0;
}