#define _CRT_SECURE_NO_WARNINGS
# include <algorithm>
# include <cstdio>
# include <set>
# include <vector>
using namespace std;

const char *FIN = "apm.in", *FOU = "apm.out";

struct muchie {
	int x, y, value;
	muchie() {
		x = y = value = 0;
	};
	muchie(int _x, int _y, int _value) {
		x = _x, y = _y, value = _value;
	};
};

/* operatorul de < pentru set */
inline bool operator < (muchie const& lhs, muchie const& rhs) {
	return (lhs.x < rhs.x) ||
		(lhs.x == rhs.x && lhs.y < rhs.y) ||
		(lhs.x == rhs.x && lhs.y == rhs.y && lhs.value < rhs.value);
}

inline bool operator == (muchie const& lhs, muchie const& rhs) {
	return lhs.x == rhs.x && lhs.y == rhs.y && lhs.value == rhs.value;
}

inline bool operator != (muchie const& lhs, muchie const& rhs) {
	return !(lhs == rhs);
}

int N, M, solution;
vector<muchie> U, T;

/* Parcurgem in adancime graful (X, T) si marcam in viz varfurile vizitate */
void dfs(int vf, vector<bool> &viz, vector<vector<bool>> &A) {
	viz[vf] = 1;
	for (int i = 1; i <= N; ++i)
		if (viz[i] == 0 && A[vf][i])
			dfs(i, viz, A);
}

void constructAdj(vector<vector<bool>> &A) {
    /* Construim matricea de adiacenta a grafului (X, T) */
	for (auto &u : T) {
		A[u.x][u.y] = A[u.y][u.x] = 1;
	}
}

muchie checkAndSolve() {
	vector<bool> viz(N + 1);
	vector<vector<bool>> A(N + 1, vector<bool>(N + 1));

	auto edge = *T.begin();
	constructAdj(A);
	dfs(edge.x, viz, A);

	for (int i = 1; i <= N; ++i) {
		/*  inseamna ca avem mai multe componente conexe, si fie
		A multimea formata din varfurile marcate din vectorul viz */
		if (viz[i] == false) {
			/* Pentru fiecare muchie din graful dat verificam daca apartine W(A)
			si luam minimul dintre toate acestea */
			muchie minEdge;
			for (auto &u : U) {
				int adj = viz[u.x] + viz[u.y];
				if (adj != 1) continue; // trebuie sa avem exact un capat in multimea A
				if (minEdge.x == 0 || (minEdge.x != 0 && minEdge.value > u.value))
					minEdge = u;
			}
			return minEdge;
		}
	}
	return muchie(-1, -1, -1); // daca avem doar 1 componenta conexa
}

int main(void) {
	freopen(FIN, "r", stdin);
	freopen(FOU, "w", stdout);

	scanf("%d %d", &N, &M);
	for (int i = 1, x, y, value; i <= M; ++i) {
		scanf("%d %d %d", &x, &y, &value);
		U.push_back(muchie(x, y, value));
		T.push_back(muchie(x, y, value));
	}

	for (auto &u : U) {
		T.erase(find(T.begin(), T.end(), u)); // T = T - {u}
		muchie result = checkAndSolve();
		if (result != muchie(-1, -1, -1)) {
			T.push_back(result); // T = T U {result}
		}
	}
	for (auto& u : T) { // calculam ponderea minima
		solution += u.value;
	}
	printf("%d\n%d\n", solution, N - 1);
	for (auto& u : T) { // afisam muchiile apm-ului
		printf("%d %d\n", u.x, u.y);
	}
}