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

#define mp make_pair

using namespace std;

const int MAX_N = 200005;

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

int n, m, tata[MAX_N], cost;
vector < pair <int, pair <int, int> > > Edge;
vector <pair <int, int> > sol;

void read() {
	f >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		f >> a >> b >> c;
		Edge.push_back (mp(c, mp(a, b)));
	}
	sort (Edge.begin(), Edge.end());
}

inline int root (int nod)
{
    int R;
 
    for (R = nod; R != tata[R]; R = tata[R]);
    for (int y; nod != R; y = nod, nod = tata[nod], tata[y] = R);
 
    return R;
}

void Unite(int x, int y) {
	int rx = root(x);
	int ry = root(y);
	
	tata[rx] = ry;
}

void solve() {
	for (int i = 1; i <= n; i++)
		tata[i] = i;
	
	for (int i = 0; i < m; i++) {
		int x = Edge[i].second.first;
		int y = Edge[i].second.second;
		
		if (root(x) != root(y)) {
			Unite(x, y);
			cost += Edge[i].first;
			sol.push_back (mp(x, y));
		}
		
	}
}

int main() {
	read();
	solve();
	
	g << cost << '\n' << n - 1 << '\n';
	for (int i = 0; i < sol.size(); i++)
		g << sol[i].first << " " << sol[i].second << '\n';
	return 0;
}