#include <cstdio>
#include <vector>
#include <set>
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) {}

	bool operator < (const edge& other) const {
		return cost < other.cost || (cost == other.cost && to < other.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);
	set<edge> candidates;
	bestDist[1].cost = 0;
	candidates.insert({0, 1});

	int result = 0;
	for (int step = 1; step <= N; step++) {
		int bestNode = candidates.begin() -> to;
		selected[bestNode] = true;
		result += bestDist[bestNode].cost;
		candidates.erase(candidates.begin());

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

	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;
}