#include <iostream>
#include <cstdio>
#include <fstream>
#include <set>
#include <vector>
#include <list>
#include <queue>
#include <algorithm>
#include <stack>

#define inf 2000000000

using namespace std;

int n, m, k, costArobre;

class edge {
public:
	int a, b, cost;
	edge() {}
	edge(int x, int y, int c) {
		a = x;
		b = y;
		cost = c;
	}
};

class compEdges {
public:
	bool operator ()(const edge& lhs, const edge& rhs) {
		return lhs.cost > rhs.cost;
	}
};

priority_queue<edge, vector<edge>, compEdges> pq;
vector<pair<int, int> > tree;
bool marked[50001];

int main()
{
	int i, j, a, b, c;
	edge* del;
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d %d", &n, &m);
	k = 1;
	for (i = 1; i <= m; i++) scanf("%d%d%d", &a, &b, &c), pq.push(*new edge(a, b, c));
	for (i = 1; i <= m; i++) {
		a = pq.top().a;
		b = pq.top().b;
		c = pq.top().cost;
		pq.pop();
		if (!(marked[a] && marked[b])) {
			tree.push_back(make_pair(a, b));
			costArobre += c;
			marked[a] = true;
			marked[b] = true;
		}
	}
	printf("%d\n", costArobre);
	printf("%d\n", n - 1);
	for (vector<pair<int, int> >::iterator it = tree.begin(); it < tree.end(); it++) {
		printf("%d %d\n", (*it).first, (*it).second);
	}

	return 0;
}