#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>

#define min(a,b) ((a)<(b))?(a):(b)
#define max(a,b) ((a)>(b))?(a):(b)

#define NMAX 200001
#define INF 0x3f3f3f3f
const char IN[] = "apm.in", OUT[] = "apm.out";

using namespace std;
struct edge {
	int s, d, c;
	edge() { s = c = d = 0; }
	edge(int s, int c, int d){
		this->s = s;
		this->c = c;
		this->d = d;
	}
};

bool comparator(edge e1, edge e2) {
	if (e1.c == e2.c) return e1.s < e2.s;
	return e1.c < e2.c;
}

int N, M;
vector<edge> edges;
vector<edge> tree;
vector<set<int> > nodes;
vector<int> node_set;

inline void readData() {
	freopen(IN, "r", stdin);
	scanf(" %d %d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int s, c, d;
		scanf(" %d %d %d", &s, &c, &d);
		edges.push_back(edge(s, d, c));
	}
	fclose(stdin);
}

inline void kruskall() {
	sort(edges.begin(), edges.end(), comparator);

	for (int i = 0; i <= N; ++i) {
		nodes.push_back(set<int>({ i }));
		node_set.push_back(i);
	}
	int cost = 0;
	for (int i = 0; tree.size() < N - 1 && i < M; ++i) {
		if (node_set[edges[i].s] != node_set[edges[i].d]) {
			int a = min(node_set[edges[i].s], node_set[edges[i].d]);
			int b = max(node_set[edges[i].s], node_set[edges[i].d]);
			tree.push_back(edges[i]);
			cost += edges[i].c;
			for (const int k : nodes[b]) {
				nodes[a].insert(k);
				node_set[k] = a;
			}
		}
	}
	freopen(OUT, "w", stdout);
	printf("%d\n%d\n", cost, tree.size());
	for (int i = 0; i < tree.size(); ++i) {
		printf("%d %d\n", tree[i].s, tree[i].d);
	}
	fclose(stdout);
}

int main() {
	readData();
	kruskall();

}