#include <fstream>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <string>

using namespace std;

ifstream fi("apm.in");
ofstream fo("apm.out");

struct node{
	int data, rang;
	node* father;
};

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

const int maxn = 200000;

node* FIND(node* a);
void UNION(node* a, node* b);
bool cmp(muchii a, muchii b);
void solve();
void init();
void show();

int N, M;
node* nodes[maxn + 1];
muchii V[2 * maxn + 2];
int SOL_X[maxn + 1], SOL_Y[maxn + 1], SOL = 0, k;


int main()
{
	init();
	solve();
	show();
	return 0;
}

void init()
{
	fi >> N >> M;
	for (int i = 1;i <= N;i++)
	{
		nodes[i] = new node;
		nodes[i]->data = i;
		nodes[i]->rang = 0;
		nodes[i]->father = NULL;
	}

	for (int i = 1;i <= M;i++)
		fi >> V[i].x >> V[i].y >> V[i].cost;

	sort(V + 1, V + M + 1, cmp);
	return;
}

bool cmp(muchii a, muchii b)
{
	if (a.cost < b.cost)
		return true;
	return false;
}

void solve()
{
	for (int i = 1;i <= M;i++)
	{
		if (FIND(nodes[V[i].x]) != FIND(nodes[V[i].y]))
		{
			UNION(nodes[V[i].x], nodes[V[i].y]);
			SOL += V[i].cost;
			SOL_X[++k] = V[i].x;
			SOL_Y[k] = V[i].y;
		}
	}
	return;
}

void UNION(node* a, node* b) 
{
	if (a->rang > b->rang)
	{
		while (b->father != NULL)
			b = b->father;
		nodes[b->data]->father = a;
	}
	else if (b->rang > a->rang)
	{
		while (a->father != NULL)
			a = a->father;
		nodes[a->data]->father = b;
	}
	else
	{
		while (a->father != NULL)
			a = a->father;
		nodes[a->data]->father = b;
		nodes[b->data]->rang++;
	}

}

node* FIND(node* a)
{
	node* n = nodes[a->data];
	if (n->father != NULL)
		n->father = FIND(n->father);
	else if (n->father == NULL)
		return n;
	return n->father;
}

void show()
{
	fo << SOL << "\n" << N - 1 << "\n";
	for (int i = 1;i <= k;i++)
		fo << SOL_Y[i] << ' ' << SOL_X[i] << "\n";
}