#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 merge(Edge e) {
	int x = rep(e.x), y = rep(e.y);
	if (x == y)
		return;
	cost_min += e.c;
	r[y] = x;
	ans.push_back({e.y, e.x});
}

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++)
		merge(e[i]);

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

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