#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAXN 200002
#define MAXM 400002

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

typedef pair < int , pair < int, int > > Edge;

int n, m, rang[MAXN], tata[MAXN];
vector <Edge> E;

void citire () {
	fin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int x, y, w;
		fin >> x >> y >> w;
		E.push_back(make_pair(w, make_pair(x, y)));
		//cout << E[i].second.first << " " << E[i].second.second << " " << E[i].first << '\n';
	}
}

void init (int rang[], int tata[]) {
	for (int i = 1; i <= n; ++i) {
		rang[i] = 0;
		tata[i] = i;
	}
}

void Union (int root1, int root2) {
	if (rang[root1] < rang[root2])
		tata[root1] = root2;
	else {
		if (rang[root1] > rang[root2]) {
			tata[root2] = root1;
		} else {
			tata[root1] = root2;
			rang[root1]++;
		}
	}
}

int find (int nod) {
	if (tata[nod] == nod)
		return nod;
	return find(tata[nod]);
}

int cmp (Edge a, Edge b) {
	return a.first < b.first;
}

void APM () {
	vector <Edge> Arb;
	int sum = 0, size = 0;
	init(rang, tata); 
	sort(E.begin(), E.end(), cmp);
	
	int root1, root2;
	for (int i = 0; i < m; ++i) {
		int x = E[i].second.first, y = E[i].second.second;
		root1 = find(x);
		root2 = find(y);
		if (root1 != root2) {
			Arb.push_back(E[i]);
			Union(root1, root2);
			sum += E[i].first;
			size++;
		}
	}
	fout << sum << '\n' << size << '\n';
	for (int i = 0; i < size; ++i) {
		fout << Arb[i].second.first << " " << Arb[i].second.second << '\n';
	}

}

int main () {
	citire();
	APM();
}