#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

struct Node {
	int rank;
	int father;
};

struct Edge {
	int cost;
	int x;
	int y;
};

void init_forest(int node, Node* forest) {
	forest[node].rank = 0;
	forest[node].father = node;
}

int find_root(int node, Node* forest) {
	if (forest[node].father != node) {
		forest[node].father = find_root(forest[node].father, forest);
	}
	return forest[node].father;		
}

void union_trees(int node_a, int node_b, Node* forest) {
	int x_root = find_root(node_a, forest);
	int y_root = find_root(node_b, forest);
	
	if (x_root == y_root) {
		return;
	}
	
	if (forest[x_root].rank < forest[y_root].rank) {
		forest[x_root].father = y_root;
	} else if (forest[x_root].rank > forest[y_root].rank) {
		forest[y_root].father = x_root;
	} else {
		forest[y_root].father = x_root;
		forest[y_root].rank += 1;
	}
}

int edge_cmp_func(Edge x, Edge y) {
	return x.cost < y.cost;
}

#define MAXN 400100

int main(int argc, char** argv) {
	int n, e;
	Node forest[MAXN];
	Edge edges[MAXN];
	
	FILE* fin = fopen("apm.in", "r");
	FILE* fout = fopen("apm.out","w");
	
	fscanf(fin, "%d%d", &n, &e);
	for (int i = 0; i < e; ++i) {
		fscanf(fin, "%d %d %d", &edges[i].x, &edges[i].y, &edges[i].cost);
	}
	fclose(fin);
	
	for (int i = 0; i < n; ++i) {
		init_forest(i, forest);
	}
	
	sort(edges, edges + e, edge_cmp_func);
	
	int answear = 0;
	vector<int> answear_edges_index;
	
	for (int i = 0; i < e; ++i) {
		if (find_root(edges[i].x, forest) != find_root(edges[i].y, forest)) {
			union_trees(edges[i].x, edges[i].y, forest);
			answear += edges[i].cost;
			answear_edges_index.push_back(i);
		}
	}

	fprintf(fout, "%d\n%d\n", answear, answear_edges_index.size());
	for (int i = 0; i < answear_edges_index.size(); ++i) {
		fprintf(fout, "%d %d\n", edges[answear_edges_index[i]].x, edges[answear_edges_index[i]].y);
	}
	fclose(fout);
	
	return 0;
}