#include <bits/stdc++.h>
 
using namespace std;

const int MAXN = 2e5 + 10;

int t[MAXN];
int card[MAXN];

int root(int x) {
	if(x == t[x]) return x;
	return t[x] = root(t[x]);
}

void unite(int x, int  y) {
	x = root(x), y = root(y);
	if(card[x] < card[y]) swap(x, y);

	t[y] = x;
	card[x] += card[y];

	return;
}

int main() {
	#ifdef BLAT
		freopen("input", "r", stdin);
	#else
		freopen("apm.in", "r", stdin);
		freopen("apm.out", "w", stdout);
	#endif
 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	vector< pair< pair< int, int >, int > > v(m);

	for(int i = 1; i <= n; ++i) {
		t[i] = i;
		card[i] = 1;
	}

	for(int i = 0; i < m; ++i) {
		cin >> v[i].first.first >> v[i].first.second >> v[i].second;
	}

	sort(v.begin(), v.end(), [&](const pair< pair< int, int >, int> &a, const pair< pair< int, int >, int > &b)-> bool{return a.second<b.second;});

	long long ans = 0;
	vector< pair< int, int > > sol;
	for(auto &x : v) {
		if(root(x.first.first) != root(x.first.second)) {
			unite(x.first.first, x.first.second);
			ans += x.second;
			sol.emplace_back(x.first);
		}
	}

	cout << ans << '\n';
	cout << sol.size() << '\n';

	for(auto &x : sol) {
		cout << x.first << ' ' << x.second << '\n';
	}
	return 0;
}