#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct {
	int x, y;
	int cost;
} edge;

edge *new_edge(int x, int y, int cost)
{
	edge *new_edge = malloc(sizeof(*new_edge));
	new_edge->x = x;
	new_edge->y = y;
	new_edge->cost = cost;
	return new_edge;
}

int cmp(const void *a, const void *b)
{
	edge *first_edge = *(edge**)a;
	edge *second_edge = *(edge**)b;
	return first_edge->cost - second_edge->cost;
}

int find_root(int x, int *father)
{
	if (x == father[x])
		return x;
	return find_root(father[x], father);
}

int kruskal(int n, int m, edge **edges, edge **span_tree)
{
	int Minimum_cost = 0;
	qsort(edges, m, sizeof(*edges), cmp);
	// for (int i = 0; i < m; i++) {
	// 	fprintf(stdout, "%d %d %d\n", edges[i]->x + 1, edges[i]->y + 1, edges[i]->cost);
	// }
	int *father = malloc(n * sizeof(*father));
	for (int i = 0; i < n; i++) {
		father[i] = i;
	}
	int cnt_edges = 0;
	for (int i = 0; i < m && cnt_edges < n - 1; i++) {
		// finds roots
		int root1 = find_root(edges[i]->x, father);
		int root2 = find_root(edges[i]->y, father);
		// check if they make part of the same conex component
		if (root1 == root2)
			continue;
		// Add to the spanning tree
		Minimum_cost += edges[i]->cost;
		span_tree[cnt_edges] = edges[i];
		cnt_edges++;
		// Union
		father[root1] = root2;
	}
	free(father);
	return Minimum_cost;
}

int main()
{
	// freopen("kruskal.in", "r", stdin);
	// freopen("kruskal.out", "w", stdout);
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	int n, m;
	scanf("%d %d", &n, &m);
	edge **edges = malloc(m * sizeof(*edges));
	for (int i = 0; i < m; i++) {
		int x, y, cost;
		scanf("%d %d %d", &x, &y, &cost);
		x--;
		y--;
		edges[i] = new_edge(x, y, cost);
	}
	edge **span_tree = malloc((n - 1) * sizeof(*span_tree));
	int Minimum_cost = kruskal(n, m, edges, span_tree);
	printf("%d\n%d\n", Minimum_cost, n - 1);
	for (int i = 0; i < n - 1; i++)
		printf("%d %d\n", span_tree[i]->x + 1, span_tree[i]->y + 1);
	// free memory
	free(span_tree);
	for (int i = 0; i < m; i++)
		if (edges[i])
			free(edges[i]);
	free(edges);
	return 0;
}