#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>

#define INF 0x3f3f3f3f

using namespace std;

vector<int> key(200005, INF);
vector<int> parrent(200005, -1);
vector<bool> added(200005, false);
vector<pair<int, int>> graph[100005];

void prim(int src) {
}

int main() {
	ifstream f("apm.in");
	int n, m;
	f >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		f >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
		graph[b].push_back(make_pair(a, c));
	}

	f.close();
	priority_queue<pair<int, int>, vector <pair<int, int>>, greater<pair<int, int>> > pq;

	key[1] = 0;
	pq.push(make_pair(0, 1));

	int maxCost = 0;
	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		added[u] = true;
		for (auto it : graph[u]) {
			int v = it.first;
			int w = it.second;

			if (added[v] == false && key[v] > w)
			{
				pq.push(make_pair(w, v));
				key[v] = w;
				parrent[v] = u;
			}
		}
	}

	for (int i = 1; i <= n; i++)
		maxCost += key[i];

	ofstream g("apm.out");
	g << maxCost << "\n";
	g << n - 1 << "\n";
	for (int i = 2; i <= n; i++) {
		g << parrent[i] << " " << i << "\n";
	}
	g.close();

}