// Kruskal.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

//#include "pch.h"
#include <iostream>
#include <fstream>
#include <deque>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

class UnionFind {
private:
	deque<int>parents;
	deque<int>size;
	int n;
public:
	void initialiseUnionFind(int n) {
		for (int i = 0; i <= n; ++i) {
			parents.push_back(i);
			size.push_back(1);;
		}
		this->n = n;
	}
	int find(int x) {
		if (parents[x] == x) {
			return x;
		}
		else 
			return find(parents[x]);
	}
	void unionSets(int x, int y) {
		int p, q;
		p = find(x);
		q = find(y);
		if (p == q) {
			return;
		}
		if (size[p] >= size[q]) {
			size[p] = size[p] + size[q];
			parents[q] = p;
		}
		else {
			size[q] = size[q] + size[p];
			parents[p] = q;
		}

	}
	bool sameComponent(int x, int y) {
		return (find(x) == find(y));
	}


};
struct Edge {
	int head;
	int tail;
	int weight;
};
struct Vertex {
	int value;
	int weight;
	Vertex * next;
};
class Graph { 
	
private:
	int nVertices, nEdges;
	bool directed;
	deque<Vertex *>adjacencyList;
	deque<bool>discovered;
	deque<bool>processed;
	deque<Edge>edges;
	deque<Edge>minimmumSpanningTree;

public:
    void sortEdgesByCost() {
		sort(edges.begin(), edges.end(), [&](const Edge & a, const Edge & b) {return a.weight < b.weight; });
        }

	void initialiseGraph() {
		for (int i = 1; i <= nVertices + 1; ++i) {
			discovered.push_back(false);
			processed.push_back(false);
			adjacencyList.push_back(nullptr);
		}
	}
	void readGraph(int nVertices, int nEdges, bool directed) {
		int x, y, weight;
		this->nVertices = nVertices;
		this->nEdges = nEdges;
		this->directed = directed;
		initialiseGraph();
		for (int i = 1; i <= nEdges; ++i) {
			fin >> x >> y >> weight;
			insertedEdge(y, x, weight, directed);
		}
	}
	void insertedEdge(int x, int y, int weight, bool directed) {
		Vertex * newVertex = new Vertex;
		newVertex->value = x;
		newVertex->weight = weight;
		newVertex->next = adjacencyList[y];
		adjacencyList[y] = newVertex;
		if (directed == false)
			insertedEdge(y, x, weight, !directed);
	}
	void bfs(int start) {
		
		int info;
		queue<int> vertices;
		vertices.push(start);
		while (!vertices.empty()) {
			info = vertices.front();
			vertices.pop();
			processed.at(info) = true;
			Vertex * p = adjacencyList.at(info);
			while (p != nullptr) {
				if (discovered.at(p->value) == false) {
					vertices.push(p->value);
					discovered.at(p->value) = true;
				}
				if (processed.at(p->value) == false || directed == true) {
					Edge newEdge;
					newEdge.head = info;
					newEdge.tail = p->value;
					newEdge.weight = p->weight;
					edges.push_back(newEdge);
				}
				p = p->next;
			}
		}
		
	}
	void kruskal() {
		bfs(1);
		sortEdgesByCost();
		int totalCost = 0;
		UnionFind disjointSets;
		disjointSets.initialiseUnionFind(nVertices);
		int j = 1;
		for (int i = 0; i < nEdges && j < nVertices ; ++i) {
			if (!disjointSets.sameComponent(edges.at(i).head, edges.at(i).tail)) {
				totalCost += edges.at(i).weight;
				disjointSets.unionSets(edges.at(i).head, edges.at(i).tail);
				minimmumSpanningTree.push_back(edges.at(i));
				++j;
			}
		}
		fout << totalCost << endl << nVertices - 1 << endl;
		for (Edge e : minimmumSpanningTree) {
			fout << e.head << " " << e.tail << endl;
		}
		
	}
	
};
int main()
{
	int nVertices, nEdges;
	fin >> nVertices >> nEdges;
	Graph g;
	g.readGraph(nVertices, nEdges, false);
	g.kruskal();
	
	return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file