#include <bits/stdc++.h>
#define MMAX 400001

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int father[MMAX], node1[MMAX], node2[MMAX], cost[MMAX], edge_index[MMAX], ans[MMAX];

int find_father(int i) {
	if(father[i] == i)
        return i;
	father[i] = find_father(father[i]);
	return father[i];
}

void unite(int i,int j) {
	father[find_father(i)] = find_father(j);
}

bool cmp(int i,int j) {
	return cost[i] < cost[j];
}

int main() {
    int n, m, min_cost = 0;
	fin >> n >> m;
	for(int i = 1; i <= m; i++) {
		fin >> node1[i] >> node2[i] >> cost[i];
		edge_index[i] = i;
	}

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

	sort(edge_index + 1, edge_index + m + 1, cmp);
	int k = 0;
	for(int i = 1; i <= m; i++) {
		if(find_father(node1[edge_index[i]]) != find_father(node2[edge_index[i]])) {
			min_cost += cost[edge_index[i]];
			unite(node1[edge_index[i]], node2[edge_index[i]]);
			ans[++k] = edge_index[i];
		}
	}
	fout << min_cost << '\n';
	fout << n - 1 << '\n';
	for(int i = 1; i <= n - 1; i++)
		fout << node1[ans[i]] << ' ' << node2[ans[i]] << '\n';
}