#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define sf second.first
#define ss second.second
#define pb push_back

using namespace std;

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

vector<pair<int, int> > graf;
priority_queue<pair<int, pair<int, int> > > heap;
int n, m, grad[200003], tata[200003], costT = 0, m_ = 0;
pair<int, pair<int, int> > p;

int findFather(int x)
{
	if (tata[x] == x)
		return x;
	else return findFather(tata[x]);
}

void read()
{
	f >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		tata[i] = i;
		grad[i] = 1;
	}

	for (int i = 0; i < m; i++)
	{
		int x, y, c;
		f >> x >> y >> c;
		heap.push({ -c, {x, y} });
	}
}

void kruskal()
{
	m_ = 0;
	costT = 0;
	while (!heap.empty() && m_ < m - 1)
	{
		int fx, fy;
		p = heap.top();
		heap.pop();
		fx = findFather(p.sf);
		fy = findFather(p.ss);

		if (fx != fy)
		{
			if (grad[fx] < grad[fy])
			{
				tata[fx] = tata[fy];
				grad[fy] += grad[fx];
			}
			else
			{
				tata[fy] = tata[fx];
				grad[fx] += grad[fy];
			}
			cout << "****" << endl;
			costT += -p.first;
			m_++;
			graf.pb({ p.sf, p.ss });
		}
	}
}

void display()
{
	g << costT << '\n';
	g << m_ << '\n';
	for (int i = 0; i < m_; i++)
		g << graf[i].first << ' ' << graf[i].second << '\n';
}

int main()
{
	read();
	kruskal();
	display();
}