#include <bits/stdc++.h>
int main() {
	using namespace std;
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	int n, m;
	fin >> n >> m;
	struct edge_t {
		int u, v, c;
		edge_t() {}
		edge_t(int u, int v, int c): u(u), v(v), c(c) {}
		bool operator <(const edge_t &oth) const {
			return c < oth.c;
		}
	};
	vector<edge_t> edges;
	edges.reserve(m);
	for(int i = 0; i < m; i++) {
		int u, v, c;
		fin >> u >> v >> c;
		u--; v--;
		edges.emplace_back(u, v, c);
	}
	sort(edges.begin(), edges.end());
	struct dsu {
		int n;
		vector<int> up, sz;
		dsu() {}
		dsu(int n): n(n), up(n), sz(n) {}
		void makeSet(int u) {
			up[u] = u;
			sz[u] = 1;
		}
		void init() {
			for(int i = 0; i < n; i++) {
				makeSet(i);
			}
		}
		int findRoot(int u) {
			if(up[u] == u) return u;
			return up[u] = findRoot(up[u]);
		}
		bool unite(int u, int v) {
			u = findRoot(u);
			v = findRoot(v);
			if(u == v) return false;
			if(sz[u] > sz[v]) {
				swap(u, v);
			}
			up[u] = v;
			sz[v] += sz[u];
			return true;
		}
	};
	dsu ds(n);
	ds.init();
	vector<edge_t> ans;
	for(const auto &[u, v, c]: edges) {
		if(ds.unite(u, v)) {
			ans.emplace_back(u, v, c);
		}
	}
	int cost = 0;
	for(const auto &[u, v, c]: ans) {
		cost += c;
	}
	fout << cost << '\n' << ans.size() << '\n';
	for(const auto &[u, v, c]: ans) {
		fout << u + 1 << " " << v + 1 << '\n';
	}
	return 0;
}