#include <fstream>
#include <queue>
#include <functional>
#define NMAX 200005
#define MMAX 400005
 
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
 
struct muchie
{
	int x, y, c;
 
	friend bool operator > (muchie, muchie);
};
 
bool operator > (muchie a, muchie b)
{
	return a.c > b.c;
}
 
priority_queue <muchie, vector <muchie>, greater<muchie> > Min_Heap;
 
int n, m, cmin;
int tata[NMAX];
int h[NMAX];
vector <muchie> a; // APM
 
void read()
{
	muchie aux;
 
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		fin >> aux.x >> aux.y >> aux.c;
		Min_Heap.push(aux);
	}
}
 
void write()
{
	fout << cmin << '\n' << n - 1 << '\n';
 
	for (int i = 0; i < n - 1; i++)
		fout << a[i].x << ' ' << a[i].y << '\n';
}
 
int Find(int x) // O(n)
{
	int rad = x, y;
 
	while (tata[rad])
		rad = tata[rad];
 
	// compresia drumului
	if (rad != x)
	{
		y = tata[x];
		while (y != rad)
		{
			tata[x] = rad;
			x = y;
			y = tata[x];
		}
	}
 
	return rad;
}
 
void Union(int x, int y)
{
	int i, j;
 
	i = Find(x);
	j = Find(y);
 
	if (i != j)
		if (h[i] < h[j])
			tata[j] = i;
		else
			if (h[i] > h[j])
				tata[i] = j;
			else
			{
				tata[i] = j;
				h[j]++;
			}
}
 
void Kruskal()
{
	muchie aux;
	int i, j;
 
	while (a.size() < n - 1)
	{
		aux = Min_Heap.top();
		Min_Heap.pop();
		i = Find(aux.x);
		j = Find(aux.y);
		if (i != j)
		{
			a.push_back(aux);
			cmin += aux.c;
			Union(i, j);
		}
	}
}
 
int main()
{
	read();
	Kruskal();
	write();
 
	return 0;
}