//Implementarea Algoritmului lui Prim cu ajutorul priority_queue-ului
//pentru determinarea arborelui partial de cost minim
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <list>

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

/*
Termeni folositi:
	cheie = costul minim
	coada de prioritate = heap de cost minim
	MST = Minimum Spanning Tree = Arbore partial de cost minim
	Prim = se refera la algoritmul lui Prim
*/

typedef std::pair<int, int> iPair; //pair of integers

const int oo = (1 << 30) - 1;

class Graph
{
private:
	int g_verticesNumber; //Numarul de puncte/noduri

	std::list < iPair >* Noduri;

public:
	//Aloca memorie pentru lista vecinilor
	Graph(int verticesNumber) //Constructor
	{
		g_verticesNumber = verticesNumber;
		Noduri = new std::list < iPair > [verticesNumber];
	}

	void AddEdge(int vertex1, int vertex2, int cost) //Functie care adauga o muchie
	{
		Noduri[vertex1].push_back(std::make_pair(vertex2, cost));
		Noduri[vertex2].push_back(std::make_pair(vertex1, cost));
	}
	
	void PrimMST(); //Functie care afiseaza arborele binar obtinut prin Algoritmul Lui Prim
};

//Afiseaza cele mai scurte drumuri de la sursa pana la celelalte noduri
void Graph::PrimMST()
{
	//Creeaza o coada de prioritate (heap de cost minim) pentru a stoca
	//nodurile care sunt procesate pentru a creea PrimMST
	std::priority_queue < iPair, std::vector <iPair>, std::greater<iPair> > p_Queue;

	int source = 1;
	//nodul 0 devine sursa;

	std::vector<int> keys(g_verticesNumber, oo);
	//Creez un vector pentru a memora muchiile cu cost minim 
	//Il initializez cu oo

	std::vector<int> parent(g_verticesNumber, -1);
	//Pentru a stoca vectorul cu parinti

	std::vector<bool> inMST(g_verticesNumber, false);
	//Aici se tine evidenta nodurilor incluse in arborele partial de cost minim

	p_Queue.push(std::make_pair(0, source));
	keys[source] = 0;
	//Inserez sursa in coada de prioritate (heap minim) si
	//initializez cheia respectiva cu 0;

	//Cat timp exista elemente in coada de prioritate
	while (p_Queue.size() > 0)
	{
		//Primul nod din coada este nodul cu cheie minima
		//este extras din coada

		int vertex = p_Queue.top().second;
		p_Queue.pop();

		inMST[vertex] = true;//Includ nodul in MST

		//folosesc 'i' pentru a cauta toti vecinii unui nod
		std::list < iPair > ::iterator i;

		for (i = Noduri[vertex].begin(); i != Noduri[vertex].end(); ++i)
		{
			//Iau nodul tata si costul nodului vecin lui "vertex"
			int TempVertex = (*i).first;
			int TempCost = (*i).second;

			//Daca TempVertex (vecinul lui vertex) nu este in MST (inMST[TempVertex] == false)
			//si costul de la vertex la TempVertex este mai mic decat costul minim din "keys"
			if (inMST[TempVertex] == false and TempCost < keys[TempVertex])
			{
				keys[TempVertex] = TempCost;
				p_Queue.push(std::make_pair(keys[TempVertex], TempVertex));
				parent[TempVertex] = vertex;
			}


		}

	}
	int sum = 0;
	for (int i = 2; i < g_verticesNumber; i++)
		sum += keys[i];
	out << sum << '\n';
	out << g_verticesNumber - 2 << '\n';
	for (int i = 2; i < g_verticesNumber; i++)
		out << parent[i] << " " << i << '\n';
}

int main()
{
	int NrNoduri, NrMuchii;
	in >> NrNoduri >> NrMuchii;
	Graph g(NrNoduri+1);

	//  Creez graful
	int tempv1, tempv2, tempc;
	for (int i = 0; i < NrMuchii; i++)
	{
		in >> tempv1 >> tempv2 >> tempc;
		g.AddEdge(tempv1, tempv2, tempc);
	}

	g.PrimMST();
	std::in.get();
}