//Kruskal
#include <iostream>
#include <fstream>
#define sizen 200010
#define sizem 400010
int n, c, v[sizen], m, price;

using namespace std;

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

struct mu
{
	int m1;
	int m2;
	int price;
	bool ok;
}muchii[sizen];

void kruskal()
{
	for(int i = 1; i <= n; i ++)
		v[i] = i;
	for(int i = 0; i < c; i ++)
	{
		if(v[muchii[i].m1] != v[muchii[i].m2])
		{
			for(int j = 1; j <= n; j ++)
				if(v[j] == v[muchii[i].m1])
					v[j] = muchii[i].m2;
			muchii[i].ok = true;
			price += muchii[i].price;
			if(i == n - 1)
				break;
		}
	}
}

int main()
{
	int x, y, p;
	f >> n >> m;
	while(f >> x >> y >> p)
	{
		muchii[c].m1 = y;
		muchii[c].m2 = x;
		muchii[c].price = p;
		muchii[c].ok = false;
		c ++;
	}
	mu aux;
	for(int i = 0; i < c - 1; i ++)
		for(int j = i + 1; j < c; j ++)
		{
			if(muchii[i].price > muchii[j].price)
			{
				aux = muchii[i];
				muchii[i] = muchii[j];
				muchii[j] = aux;
			}
		}
	kruskal();
	g << price << "\n" << n - 1 << "\n";
	for(int i = 0; i < m; i ++)
		if(muchii[i].ok)
			g << muchii[i].m1 << " " << muchii[i].m2 << "\n";
}