#include <cstdio>
#include <vector>
using namespace std;
const int NMAX = 200505;
const int INF = 0x3f3f3f3f;

struct edge {
	int cost, to;

	edge() {
		cost = INF;
		to = -1;
	}

	edge(int _cost, int _to) : cost(_cost), to(_to) {}
};

int N, M;
vector<edge> G[NMAX];

void read() {
	scanf("%d%d", &N, &M);
	int x, y, cost;
	for (int edgeIdx = 0; edgeIdx < M; edgeIdx++) {
		scanf("%d%d%d", &x, &y, &cost);
		G[x].push_back({cost, y});
		G[y].push_back({cost, x});
	}
}

void solve() {
	vector<bool> selected(N + 1, false);
	vector<edge> bestDist(N + 1);
	bestDist[1].cost = 0;

	int result = 0;
	for (int step = 1; step <= N; step++) {
		int bestNode = -1;
		for (int node = 1; node <= N; node++) {
			if (!selected[node] && (bestNode == -1 || (bestDist[bestNode].cost > bestDist[node].cost))) {
				bestNode = node;
			}
		}

		selected[bestNode] = true;
		result += bestDist[bestNode].cost;
		for (auto& outgoingEdge : G[bestNode]) {
			if (!selected[outgoingEdge.to] && bestDist[outgoingEdge.to].cost > outgoingEdge.cost) {
				bestDist[outgoingEdge.to] = {outgoingEdge.cost, bestNode};
			}
		}
	}

	printf("%d\n", result);
	printf("%d\n", N - 1);
	for (int i = 2; i <= N; i++) {
		printf("%d %d\n", i, bestDist[i].to);
	}
}

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

	read();
	solve();
	return 0;
}