#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct Edge {
	int start, finish, cost;
};

struct Graph {
	int V, E;
	struct Edge* edge;
};

struct Graph* createGraph(int V, int E)
{
	struct Graph* graph = new Graph;
	graph->V = V;
	graph->E = E;
	graph->edge = new Edge[E];
	return graph;
}

struct subset {
	int parent;
};

int root(struct subset subsets[] ,int i)
{
	if (subsets[i].parent != i)
		subsets[i].parent = root(subsets ,subsets[i].parent);
	return subsets[i].parent;
}

void unify(struct subset subsets[], int a, int b)
{
	int root_a = root(subsets, a);
	int root_b = root(subsets, b);
    subsets[root_a].parent = root_b;
}

int comp(const void* a, const void* b)
{
	struct Edge* a1 = (struct Edge*)a;
	struct Edge* b1 = (struct Edge*)b;
	return a1->cost - b1->cost;
}

void Kruskal(struct Graph *graph)
{
    int tCost = 0;
	const int V = graph->V;
	struct Edge results[V-1];
	int nEdges = 0;
	int i = 0;
    int (*C)(const void *, const void *);
    C = comp;
	qsort(graph->edge, graph->E, sizeof(struct Edge), C);
	struct subset* subsets = (struct subset*)malloc(V * sizeof(struct subset));

	for (int v = 0; v <= V; v++)
		subsets[v].parent = v;

	while (nEdges < V - 1)
	{
		struct Edge nextEdge = graph->edge[i++];

		int root_a = root(subsets, nextEdge.start);
		int root_b = root(subsets, nextEdge.finish);

		if (root_a != root_b) {
			results[nEdges++] = nextEdge;
			tCost += nextEdge.cost;
			unify(subsets, root_a, root_b);
		}
	}

	out << tCost << endl << nEdges << endl;
	for (i = 0; i < nEdges; i++)
	{
		out << results[i].start << " " << results[i].finish << endl;
	}
}

int main()
{
	int V, E;
	in >> V >> E;
	struct Graph* graph = createGraph(V, E);
	for (int i = 0; i < graph->E; i++)
	{
		in >> graph->edge[i].start >> graph->edge[i].finish >> graph->edge[i].cost;
	}
	Kruskal(graph);
}