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

typedef struct {
	int n, m;
	int **adj;
} graph;

typedef struct {
	int x, y;
} edge;

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

graph *init_graph(int n, int m)
{
	graph *graph = malloc(sizeof(*graph));
	graph->n = n;
	graph->m = m;
	graph->adj = malloc(n * sizeof(*graph->adj));
	int *aux = malloc(n * n * sizeof(int));
	for (int i = 0; i < n; i++)
		graph->adj[i] = (aux + i * n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			graph->adj[i][j] = INT_MAX;
	return graph;
}

int min(int a, int b)
{
	if (a < b)
		return a;
	return b;
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	int n, m;
	scanf("%d %d", &n, &m);
	graph *graph = init_graph(n, m);
	for (int i = 0; i < m; i++) {
		int x, y, cost;
		scanf("%d %d %d", &x, &y, &cost);
		x--;
		y--;
		if (graph->adj[x][y] == INT_MAX)
			graph->adj[x][y] = cost;
		else
			graph->adj[x][y] = min(graph->adj[x][y], cost);
		graph->adj[y][x] = cost;
	}
	int root = 0;
	// distances array
	int *dist = malloc(n * sizeof(*dist));
	int *parent = malloc(n * sizeof(*parent));
	for (int i = 0; i < n; i++) {
		dist[i] = graph->adj[root][i];
		if (dist[i] != INT_MAX)
			parent[i] = root;
		else
			parent[i] = INT_MAX;
	}
	dist[root] = 0;
	parent[root] = -1;
	// marked array
	int *marked = malloc(n * sizeof(*marked));
	memset(marked, 0, n * sizeof(*marked));
	marked[root] = 1;
	// Minimum cost
	int Minimum_cost = 0;
	// Spanning tree
	edge **spann_tree = malloc((n - 1) * sizeof(*spann_tree));
	// find all the edges from spanning tree
	for (int step = 0; step < n - 1; step++) {
		// find the next node to connect with it
		int Min = INT_MAX, poz_min = -1;
		for (int i = 0; i < n; i++)
			if (!marked[i] && Min > dist[i]) {
				Min = dist[i];
				poz_min = i;
			}
		if (poz_min == -1)
			break;
		// Update the Minimum cost
		Minimum_cost += dist[poz_min];
		marked[poz_min] = 1;
		// put the edge into the spann tree
		spann_tree[step] = new_edge(parent[poz_min], poz_min);
		// Update distances
		for (int i = 0; i < n; i++)
			if (!marked[i] && dist[i] > graph->adj[poz_min][i]) {
				dist[i] = graph->adj[poz_min][i];
				parent[i] = poz_min;
			}
	}
	printf("%d\n%d\n", Minimum_cost, n - 1);
	for (int i = 0; i < n - 1; i++)
		printf("%d %d\n", spann_tree[i]->x + 1, spann_tree[i]->y + 1);

	// free memory
	free(dist);
	free(parent);
	for (int i = 0; i < n - 1; i++)
		if (spann_tree[i])
			free(spann_tree[i]);
	free(spann_tree);
	free(graph->adj[0]);
	free(graph->adj);
	free(graph);
	return 0;
}