#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <set>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct Muchie
{
	int x, y, cost;
};

const int nmax = 200005;
Muchie muchii[nmax];
int viz[nmax];
int n, m;
int rang[nmax];
int dad[nmax];
int cost_total;
vector < Muchie > apm;

int do_find(int nod) {
	if (nod != dad[nod]) {
		int repr = do_find(dad[nod]);
		dad[nod] = repr;
		return repr;
	}
	return nod;
}

void do_union(int x, int y)
{
	if (rang[x] < rang[y])
	{
		dad[x] = y;
	}
	else if (rang[y] < rang[x])
	{
		dad[y] = x;
	}
	else {
		dad[x] = y;
		rang[y]++;
	}
}

int main()
{
	f >> n >> m;
	int a, b, c;
	for (int i = 1; i <= m; i++)
	{
		f >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
	}
	sort(muchii + 1, muchii + m + 1, [](Muchie a, Muchie b)
		{
			return a.cost < b.cost;
		});
	for (int i = 1; i <= n; i++)
	{
		dad[i] = i;
		rang[i] = 1;
	}

	int nr_muchii = 0;

	for (int i = 1; i <= m && nr_muchii <= n - 1; i++)
	{
		int reprezent_x = do_find(muchii[i].x);
		int reprezent_y = do_find(muchii[i].y);

		if (reprezent_x != reprezent_y)
		{
			do_union(reprezent_y,reprezent_x);
			nr_muchii++;
			cost_total += muchii[i].cost;
			apm.push_back(muchii[i]);
		}
	}

	g << cost_total << "\n";
	g << n - 1 << "\n";

	for (Muchie edge : apm) {
		g << edge.y << " " << edge.x << "\n";
	}
}