#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("apm.in");
ofstream fout("apm.out");
#endif

const int NMAX = 2e5+5;
const int MMAX = 2e5+5;

struct Edge {
	int x, y, c;
};

int n, m;
Edge e[MMAX];
int r[NMAX];
int sz[NMAX];
int cost_min;
vector<pair<int, int>> ans;

void read() {
	fin >> n >> m;
	
	for (int i = 1; i <= m; i++)
		fin >> e[i].x >> e[i].y >> e[i].c;
}

int rep(int x) {
	return r[x] == x ? x : rep(r[x]);
}

bool cmp(const Edge &a, const Edge &b) {
	return a.c < b.c;
}

void solve() {
	for (int i = 1; i <= n; i++) {
		r[i] = i;
		sz[i] = 1;
	}

	sort(e + 1, e + m + 1, cmp);

	for (int i = 1; i <= m; i++) {
		if (rep(e[i].x) != rep(e[i].y)) {
			int x = e[i].x, y = e[i].y;
			ans.push_back({y, x});
			if (sz[x] > sz[y])
				swap(x, y);
			sz[x] += sz[y];
			sz[y] = 0;
			r[x] = rep(y);
			cost_min += e[i].c;
		}
	}

	fout << cost_min << '\n' << ans.size() << '\n';
	for (auto a : ans)
		fout << a.first << ' ' << a.second << '\n';
}

int32_t main() {
	read();
	solve();
	return 0;
}