#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define let(X, A) typeof(A) X(A)

struct edge {
	int w;
	int u;
	int v;
	edge ( int w, int u, int v ) : w(w), u(u), v(v) {}
	bool operator > (  const edge & a ) const {
		return w > a.w;
	}
};

int main() {
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	int n, m;
	fin >> n >> m;
	vector<edge> adjl[n+1];
	for (int u, v, w, i=0; i<m; ++i) {
		fin >> u >> v >> w;
		adjl[u].push_back( edge(w, u, v) );
		adjl[v].push_back( edge(w, v, u) );
	}
	priority_queue< edge, vector<edge>, greater<edge> > pq;
	vector<bool> intree(n+1);
	intree[1] = true;
	for (let( it, adjl[1].begin() ); it != adjl[1].end(); ++it) {
		pq.push( *it );
	}
	vector<edge> mst;
	int sum = 0;

	while (!pq.empty()) {
		int v = pq.top().v;
		if (intree[v]) {
			pq.pop();
			continue;
		}
		intree[v] = true;
		mst.push_back( pq.top() );
		sum += pq.top().w;
		pq.pop();
		for (let(it, adjl[v].begin()); it != adjl[v].end(); ++it) {
			if ( !intree[ it->v ] )
				pq.push( *it );
		}
	}

	fout << sum << '\n';
	fout << n-1 << '\n';
	for (let(it, mst.begin()); it != mst.end(); ++it) {
		fout << it->u << ' ' << it->v << '\n';
	}
	return 0;
}