#include <fstream>
#include <algorithm>
#include <vector>

#define input "apm.in"
#define output "apm.out"
#define MAX_NODES 200005
#define MAX_EDGES 400005

using namespace std;

ifstream in(input);
ofstream out(output);

int father[MAX_NODES];
int find_father(int nod)
{
	if (father[nod] == nod) return nod;
	while (father[nod] != nod) nod = father[nod];
	return father[nod];
}
void Reunion(int nod1, int nod2)
{
	father[find_father(nod1)] = find_father(nod2);
}

struct muchie
{
	int x, y, cost;
} muchii[MAX_EDGES], sol_kruskal[MAX_EDGES];
int N, M;

bool sort_criteria(muchie a, muchie b)
{
	return a.cost < b.cost;
}

void Read_Data()
{
	in >> N >> M;
	for (int i = 1; i <= M; i++)
	{
		int x, y, c;
		in >> x >> y >> c;
		muchii[i] = { x, y, c };
	}
}

void Kruskal()
{
	int cost_min = 0, sol_size = 0;
	sort(muchii + 1, muchii + 1 + M, sort_criteria);
	for (int i = 1; i <= N; i++)
		father[i] = i;
	for (int i = 1; i < M; i++)
	if (find_father(muchii[i].x) != find_father(muchii[i].y))
	{
		cost_min += muchii[i].cost;
		Reunion(muchii[i].x, muchii[i].y);
		sol_kruskal[++sol_size] = muchii[i];
	}
	out << cost_min << "\n" << sol_size << "\n";
	for (int i = 1; i < sol_size; i++)
		out << sol_kruskal[i].x << " " << sol_kruskal[i].y << "\n";
}

int main()
{
	Read_Data();
	Kruskal();
	return 0;
}