// Algoritm Kruskal - Union Find.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#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;
	father[nod] = find_father(father[nod]);
	return father[nod];
}
void Reunion(int nod1, int nod2)
{
	father[find_father(nod1)] = find_father(nod2);
}

struct muchie
{
	int x, y, cost;
};
vector < muchie > muchii;
vector < muchie > sol_kruskal;
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.push_back({ x, y, c });
	}
}

void Kruskal()
{
	int cost_min = 0;
	sort(muchii.begin(), muchii.end(), sort_criteria);
	for (int i = 1; i <= N; i++)
		father[i] = i;
	for (unsigned i = 0; i < muchii.size(); 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.push_back(muchii[i]);
	}
	out << cost_min << "\n" << sol_kruskal.size() << "\n";
	for (unsigned i = 0; i < sol_kruskal.size(); i++)
		out << sol_kruskal[i].x << " " << sol_kruskal[i].y << "\n";
}

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