#include <bits/stdc++.h>
#include <cstdio>
#include <istream>

struct dsu {
	std::vector<int> p, o;

	void reset(int len) {
		p.resize(len);
		o.resize(len);
		std::fill(o.begin(), o.end(), 1);
		for(int i = 0; i < len; i++) p[i] = i;
	}

	int find(int t) noexcept {
		while(t != p[t]) t = p[t] = p[p[t]];
		return t;
	}

	bool same_set(int a, int b) noexcept { return find(a) == find(b); }

	void merge(int a, int b) noexcept { 
		a = find(a); b = find(b); 
		if(a == b) return;

		if(o[a] < o[b]) std::swap(a, b);
		p[b] = a;
		o[a] += o[a] == o[b];
	}
};

struct edge { int a, b, c; constexpr bool operator< (const edge& o) const noexcept { return c < o.c; } };
std::istream& operator>>(std::istream& is, edge& e) { is >> e.a >> e.b >> e.c; return is; }

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	int n, m; std::cin >> n >> m;
	dsu set; set.reset(n + 5);

	std::vector<edge> edges(m);
	for(auto& e: edges) std::cin >> e;
	std::sort(edges.begin(), edges.end());

	int suma = 0;
	std::vector<edge> apm;
	for(auto& e : edges) {
		if(set.same_set(e.a, e.b)) continue;
		suma += e.c;
		set.merge(e.a, e.b);
		apm.emplace_back(e);
	}

	std::cout << suma << '\n' << apm.size() << '\n';
	for(auto& e: apm) std::cout << e.a << ' ' << e.b << '\n';
	return 0;
}