#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>  

using namespace std;

const int Nmax = 200000;
const int Mmax = 400000;

struct Elem {
	int a, b, c;
} G[Mmax];

int n, m;
int  rg[Nmax], tata[Nmax];

bool comp(Elem i, Elem j);

void citire() {
	ifstream f("apm.in");
	int  i;
	f >> n >> m;
	for (i = 0; i < m; i++) 
		f >> G[i].a >> G[i].b >> G[i].c;
	f.close();
	sort(G, G + m, comp);
}

bool comp(Elem i, Elem j) {
	return (i.c < j.c);
}

int urca(int x) {
	int y, a = x;
	while (tata[x] != x)
		x = tata[x];
	while (tata[a] != x) {
		y = tata[a];
		tata[a] = x;
		a = y;
	}
	return x;
}

void unire(int a, int b) {
	if (rg[a] > rg[b]) {
		rg[a]++;
		tata[b] = a;
	}
	else {
		rg[b]++;
		tata[a] = b;
	}
}

void creare()
{
	int i, v[Nmax], j = 0, s = 0;
	for (i = 1; i <= n; i++) {
		rg[i] = 1;
		tata[i] = i;
	}
	for (i = 0; i <= m; i++) {
		if (urca(G[i].a) != urca(G[i].b)) {
			unire(tata[G[i].a], tata[G[i].b]);
			v[j] = i;
			j++;
			s += G[i].c;
		}
	}
	ofstream g("apm.out");
	g << s << "\n" << j << "\n";
	for (i = 0; i < j; i++)
		g << G[v[i]].b << ' ' << G[v[i]].a << "\n";
	g.close();
}

	int main() {
		citire();
		creare();
		//cin.get();
		return 0;
	}