#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct edge {
	int x, y, c;
	bool operator <(edge a) const {
		return c > a.c;
	}
};
struct deseu {
	vector<int> parent;
	vector<int> sz;
	void build(int n) {
		parent = sz = vector<int>(n + 1);
	}
	void make_set(int x) {
		parent[x] = x;
		sz[x] = 1;
	}
	int find_set(int v) {
		if (v == parent[v]) {
			return v;
		}
		return parent[v] = find_set(parent[v]);
	}
	void unite(int a ,int b) {
		a = find_set(a);
		b = find_set(b);
		if (a != b) {
			if (sz[a] < sz[b]) {
				swap(a, b);
			}
			parent[b] = a;
			sz[a] += sz[b];
		}
	}
};
int main() {
	int n,m;
	fin >> n >> m;
	priority_queue<edge> pq;
	deseu tree;
	tree.build(n + 1);
	for (int i = 1; i <= n; ++i) {
		tree.make_set(i);
	}
	for (int i = 1; i <= m; ++i) {
		int x, y, c;
		fin >> x >> y >> c;
		pq.push({ x,y,c });
	}
	int cost = 0;
	vector <edge> sol;
	while (!pq.empty()) {
		edge top = pq.top();
		if (tree.find_set(top.x) != tree.find_set(top.y)) {
			tree.unite(top.x, top.y);
			cost += top.c;
			sol.push_back(top);
		}
		pq.pop();
	}
	fout << cost << '\n';
	fout << (int)sol.size() << '\n';
	for (auto i : sol) {
		fout << i.x << ' ' << i.y << '\n';
	}

}