#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, cost;
	muchie() {
		x = y = cost = 0;
	};
	muchie(int _x, int _y, int _cost) {
		x = _x, y = _y, cost = _cost;
	};
};

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

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

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

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) {
	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.cost > u.cost))
					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.insert(muchie(x, y, value));
	}

	for (auto &u : U) {
		T.erase(u);
		muchie result = checkAndSolve();
		if (result != muchie(-1, -1, -1)) {
			T.insert(result);
		}
	}
	for (auto& u : T) {
		solution += u.cost;
	}
	printf("%d\n%d\n", solution, N - 1);
	for (auto& u : T) {
		printf("%d %d\n", u.x, u.y);
	}
}