#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct vectoR {
	int x, y, cost;
};
int n,m;
vectoR v[400001];
int rang[200001], t[200001],k;
pair<int, int>afisare[200001];
int crit(vectoR a, vectoR b)
{
	return(a.cost < b.cost);
}
void marcare_tata(int* v)
{
	for (int i = 1; i <= n; i++)
		v[i] = i,rang[i]=1;
}
void uneste(int x, int y)
{
	
	if (rang[y] < rang[x])
		t[y] = x;
	else
	{
		t[x] = y;
		rang[y]++;
	}
}
int answer = 0;
int radacina(int a)
{
	if (a == t[a])
		return a;
	return t[a] = radacina(t[a]);
	
}
void kruskal()
{
	int a, b;
	for (int i = 1; i <= m; i++)
	{
		a = radacina(v[i].x);
		b = radacina(v[i].y);
		if (a != b)
		{
			afisare[++k].first = v[i].x;
			afisare[k].second = v[i].y;
			answer+=v[i].cost;
			uneste(b, a);
		}
	}
}
int main() {
	f >> n>>m;
	for (int i = 1; i <= m; i++)
	{
		f >> v[i].x >> v[i].y >> v[i].cost;
	}
	marcare_tata(t);
	
	sort(v + 1, v + m + 1,crit);
	kruskal();
	g << answer << endl;
	g << k << endl;
	for (int i = 1; i <= k; i++)
		g << afisare[i].first << " " << afisare[i].second<<endl;
}