#include <bits/stdc++.h>
#define NMAX 200010

using namespace std;

struct edge {
	int x;
	int y;
	int c;
};

bool cmp(const struct edge& edge1, const struct edge& edge2) {
    return edge1.c < edge2.c;
}

int n, m, cost_apm;
int root[NMAX];
vector<edge> edges;
vector<edge> apm;

void read_input() {
	ifstream fin("apm.in");

	fin >> n >> m;

	for (int i = 1; i <= m; ++i) {
		int x, y, c;
		fin >> x >> y >> c;

		struct edge to_be_added;
		to_be_added.x = x;
		to_be_added.y = y;
		to_be_added.c = c;

		edges.push_back(to_be_added);
	}

	fin.close();
}

int get_set(int node) {
  	if (root[node] != node) {
    	root[node] = get_set(root[node]);
  	}

  	return root[node];
}

void reunion_set(int x, int y) { 
	root[get_set(x)] = get_set(y); 
}

void Kruskal() {
	sort(edges.begin(), edges.end(), cmp);

	for (int i = 1; i <= n; ++i) {
		root[i] = i;
	}

	cost_apm = 0;

	for (auto &edge : edges) {
		if (get_set(edge.x) != get_set(edge.y)) {
			cost_apm += edge.c;
			apm.push_back(edge);
			reunion_set(edge.x, edge.y);
		}
	}
}

void print_output() {
	ofstream fout("apm.out");

	fout << cost_apm << "\n";
	fout << apm.size() << "\n";

	for (auto &edge : apm) {
		fout << edge.x << " " << edge.y << "\n";
	}

	fout.close();
}



int main() {
	read_input();
	Kruskal();
	print_output();

	return 0;
}