#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
#define ech(It, A) for (__typeof(A.begin()) It = A.begin(); It != A.end(); ++It)

class DisjSet
{
	vector<int> parent;

public:
	DisjSet( int n ) {
		parent.assign(n, -1);
	}

	int find( int x ) {
		if (parent[x] < 0) return x;
		else return parent[x] = find(parent[x]);
	}

	void join( int root1, int root2 ) {
		if (parent[root1] == parent[root2]) {
			parent[root2] = root1;
			parent[root1]--;
		}
		else if (parent[root1] < parent[root2]) {
			parent[root2] = root1;
		}
		else {
			parent[root1] = root2;
		}
	}
};

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> edgl;
	DisjSet ds(n);

	for (int u, v, w, i=0; i<m; ++i) {
		fin >> u >> v >> w;
		edgl.push_back( edge(w, u, v) );
	}

	sort(edgl.begin(), edgl.end());
	int sum = 0;
	vector<vector<edge>::iterator> mst;

	ech(it, edgl) {
		int root1 = ds.find(it->u);
		int root2 = ds.find(it->v);
		if (root1 != root2) {
			ds.join(root1, root2);
			mst.push_back(it);
			sum += it->w;
		}
	}

	fout << sum << '\n';
	fout << n-1 << '\n';
	ech( it, mst ) {
		fout << (*it)->u << ' ' << (*it)->v << '\n';
	}


	return 0;
}