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

#define NMAX 200002

int N, M;

/* Reprezentarea structurii de date 'disjoint-set' */
struct subset {
	int parent;
	int rank;
} v[NMAX];

void makeSets();
int findSet(int);
void unionSets(int, int);
/* ------------------------------------------------ */

/* Reprezentarea grafului */
struct Edge {
	int u, v;
	long long cost;
	
	Edge(int u, int v, long long cost) : u(u), v(v), cost(cost) {}

	bool operator==(const Edge& e) {
		return (u == e.u) && (v == e.v) && (cost == e.cost);
	}
};

bool costCmp(const Edge& e1, const Edge& e2) {
	return e1.cost < e2.cost;
}

using Graph = std::vector<Edge>;
Graph graph;
/* --------------------------------------------------------- */

long long cost = 0;

std::vector<std::pair<int, int> > kruskal() {
	std::vector<std::pair<int, int> > MST;
	makeSets();
  	std::sort(graph.begin(), graph.end(), costCmp);

	for (Edge edge : graph) {
		/* Determin seturile din care face parte fiecare capat al muchiei */
		int set_x = findSet(edge.u);
		int set_y = findSet(edge.v);

		/* Daca aceste 2 subseturi difera, inseamna ca nu se formeaza ciclu */
		if (set_x != set_y) { 
			cost += edge.cost;
			MST.push_back(std::make_pair(edge.u, edge.v)); 
			unionSets(edge.u, edge.v); 
		}
	}

	return MST;
}


int main() {
	std::ifstream f("apm.in");
	std::ofstream g("apm.out");

	f >> N >> M;
	for (int i = 0; i < M; ++i) {
		int u, v, cost;
		f >> u >> v >> cost;
		graph.push_back(Edge(u, v, cost));
	}

	std::vector<std::pair<int, int> > MST = kruskal();
	g << cost << '\n' << N-1 << '\n';
	for (int i = 0; i < N-1; ++i) {
		g << MST[i].first << " " << MST[i].second << '\n';
	}

	f.close(); g.close();

	return 0; 
}

/* Crearea seturilor initiale: la inceput fiecare nod reprezinta un arbore independent */
void makeSets() {
	for (int i = 1; i <= N; ++i) {
		v[i].parent = i;
		v[i].rank = 0;
	}
}

int findSet(int node) {
	if (v[node].parent == node) {
		return node; /* Daca parintele este chiar nodul atunci am gasit subsetul*/
	}

	/* Altfel merg recursiv spre radacina, aplicand si compresia*/
	return (v[node].parent = findSet(v[node].parent));
}

/* Imbina 2 seturi rezultand unul singur */
void unionSets(int node1, int node2) {
	int set_x = findSet(node1);
	int set_y = findSet(node2);

	// Daca fac parte din acelasi subset - nu facem nimic
	if (set_x == set_y) {
		return;
	}

	/* Incrementam rangul doar daca unul din noduri devine parintele celuilalt*/
	if (v[set_x].rank == v[set_y].rank) {
		v[set_y].parent = set_x;
		v[set_x].rank++;

	}

	/* Cine are rang mai mare devine parintele celuilalt */
	if (v[set_x].rank > v[set_y].rank) {
		v[set_y].parent = set_x;
	} else if (v[set_x].rank < v[set_y].rank) {
		v[set_x].parent = set_y;
	}
}