#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>

#define MAXN 200002
#define foreach(V) for(vector < pair<int, int> > :: iterator it = (V).begin(); it != (V).end(); ++it)

using namespace std;

int N, M, T[MAXN], Heap[MAXN], minE[MAXN], used[MAXN], _size, H_pos[MAXN];

vector < pair<int, int> > G[MAXN];

inline void percolate(int pos) {
	int curr = Heap[pos];
	int now = pos, next = now >> 1;

	for (; next && minE[Heap[next]] > minE[curr]; Heap[now] = Heap[next], H_pos[Heap[now]] = now, now = next, next >>= 1);
	Heap[now] = curr;
	H_pos[curr] = now;
}

inline void pop_heap() {
	Heap[1] = Heap[_size--];

	int curr = Heap[1];
	int now = 1, next = 2;
	if (next + 1 <= _size && minE[Heap[3]] < minE[Heap[2]]) ++next;

	while (next <= _size && minE[Heap[next]] < minE[curr]) {
		Heap[now] = Heap[next];
		H_pos[Heap[now]] = now;
		now = next;
		next <<= 1;
		if (next + 1 <= _size && minE[Heap[next + 1]] < minE[Heap[next]]) ++next;
	}
	Heap[now] = curr;
	H_pos[curr] = now;
}

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

	int ans = 0;
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= M; ++i) {
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);

		G[x].push_back(make_pair(y, c));
		G[y].push_back(make_pair(x, c));
	}

	Heap[++_size] = 1;
	memset(minE + 2, 0x7F, sizeof(minE[0]) * N);

	while (_size) {
		int node = Heap[1];
		pop_heap();
		if (used[node]) continue;
		used[node] = 1;
		ans += minE[node];

		foreach(G[node])
			if (!used[it->first] && minE[it->first] > it->second) {
				T[it->first] = node;
				minE[it->first] = it->second;
				if (!H_pos[it->first])
					Heap[++_size] = it->first,
					H_pos[it->first] = _size,
					percolate(_size);
				else percolate(H_pos[it->first]);
			}
	}

	printf("%d\n%d\n", ans, N - 1);
	for (int i = 2; i <= N; ++i) {
		if (!used[i]) continue;

		for (int node = i; node != 1 && used[node]; node = T[node])
			printf("%d %d\n", node, T[node]),
			used[node] = 0;
	}


	return 0;
}