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

#define NMAX 200005
#define MMAX 400005
#define problem "apm"

class DSU {
private:
	vector<int> rank, rep;

	int find_rep(int x) {
		if (rep[x] == x)
			return x;
		return rep[x] = find_rep(rep[x]);
	}

public:
	DSU(int n) : rank(n + 1), rep(n + 1) {
		for (int i = 1; i <= n; ++i)
			rep[i] = i;
	}

	void unite(int x, int y) {
		int rep_x = find_rep(x), rep_y = find_rep(y);

		if (rank[rep_x] < rank[rep_y]) {
			++rank[rep_y];
			rep[rep_x] = rep_y;
		} else {
			++rank[rep_y];
			rep[rep_x] = rep_y;
		}
	}

	bool check(int x, int y) {
		return find_rep(x) == find_rep(y);
	}
};

struct edge {
	int x, y, c;

	bool operator < (const edge &e) {
		return c < e.c;
	}
};

int main() {
	freopen(problem ".in", "r", stdin);
	freopen(problem ".out", "w", stdout);

	int n, m;
	scanf("%d%d", &n, &m);

	DSU d(n);

	vector<edge> edges(m);

	for (edge &e : edges)
		scanf("%d%d%d", &e.x, &e.y, &e.c);

	sort(edges.begin(), edges.end());

	int cost = 0;
	vector<edge> sol(n - 1);

	vector<edge>::iterator it = edges.begin();

	for (int i = 0; i < n - 1; ++i) {
		while (d.check((*it).x, (*it).y))
			++it;
		d.unite((*it).x, (*it).y);
		cost += (*it).c;
		sol[i] = *it;
	}

	printf("%d\n%d\n", cost, n - 1);

	for (const edge &e : sol)
		printf("%d %d\n", e.x, e.y);
}