#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <iterator>
#include <queue>
#include <functional>
#include <utility>
#define MAXN 200005
#define MAXM 400005

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int p[MAXN], Rank[MAXN];

struct LM {
	int x, y, c;
} aux;
struct {
	int x, y;
} final[MAXN];

class comp {
public:
	bool operator() (const LM &A, const LM &B) {
		return A.c > B.c;
	}
};

int findSet(int i);
bool inSameSet(int i, int j);
void unionSet(int i, int j);

int main() {
	int n, i, x, y, c, m, muchiiSelectate;

	fin >> n >> m;

	priority_queue < LM, vector<LM>, comp > pq;

	for (i = 0; i < m; ++i) {
		fin >> x >> y >> c;

		aux.x = x;
		aux.y = y;
		aux.c = c;

		pq.push(aux);
	}

	for (i = 1; i <= n; ++i)
		p[i] = i;

	int total = muchiiSelectate = 0;
	while (muchiiSelectate < n - 1) {
		aux = pq.top();
		pq.pop();

		if (!inSameSet(aux.x, aux.y)) {
			total += aux.c;

			unionSet(aux.x, aux.y);

			final[muchiiSelectate].x = aux.x;
			final[muchiiSelectate].y = aux.y;

			++muchiiSelectate;
		}
	}

	fout << total << '\n' << n - 1 << '\n';

	for (i = 0; i < n - 1; ++i)
		fout << final[i].x << ' ' << final[i].y << '\n';

	return 0;
}

int findSet(int i) {
	if (p[i] == i)
		return i;

	return p[i] = findSet(p[i]);
}

bool inSameSet(int i, int j) {
	return findSet(i) == findSet(j);
}

void unionSet(int i, int j) {
	int x = findSet(i);
	int y = findSet(j);

	p[x] = y;
}