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

using namespace std;

typedef unsigned long ulong;
typedef unsigned int uint;

template<class T, class Comparator = std::less<T> >
class BinaryHeap
{
	public:
		BinaryHeap(uint size = 128) { _storage.reserve(size); }
		
	public:
		T peek() const { return _storage.front(); }
		
		T pop()
		{
			T data = _storage.front();
			
			_storage[0] = _storage.back();
			_storage.pop_back();
			
			siftDown(0);
						
			return data;
		}
		
		void push(const T& data) 
		{
			_storage.push_back(data);
			siftUp(size()-1);
		}
		
		bool empty() const { return !size(); }		
		uint size() const { return _storage.size(); }		
		bool contains(T const& data) const { return find(data) != -1; }
		
	public:
		Comparator& getComparator() { return comp; }
		
	private:
		uint parent 	(uint index) const { return (index-1)/2; }
		uint leftChild 	(uint index) const { return 2*index+1; }
		uint rightChild	(uint index) const { return 2*index+2; }
		
		bool hasLeftChild 	(uint index) const { return 2*index+1 < size(); }	
		bool hasRightChild 	(uint index) const { return 2*index+2 < size(); }
		bool hasChildren	(uint index) const { return hasLeftChild(index); }
		
		bool isRoot		(uint index) const { return index == 0; }
		bool hasParent	(uint index) const { return !isRoot(index); }
		
		int find(T const& data) const
		{
			typename std::vector<T>::const_iterator found = std::find(_storage.begin(), _storage.end(), data);
			
			if(found == _storage.end()) {				
				return -1;
			} else {
				return found - _storage.begin();
			}
		}
	
		uint getHigherPriorityIndex(uint firstIndex, uint secondIndex) const 
		{
			if(comp(_storage[firstIndex], _storage[secondIndex]))
				return firstIndex;
			else
				return secondIndex;
		}
		
		//	Takes an item's index (must have at least one child) and returns the index of the "higher priority" child
		uint getHigherPriorityChildIndex(uint parentIndex) const
		{
			//	Assume the left child has higher priority
			uint highestPriorityChildIndex = leftChild(parentIndex);
			
			if(hasRightChild(parentIndex)) {
				highestPriorityChildIndex = getHigherPriorityIndex(
					highestPriorityChildIndex,
					rightChild(parentIndex)
				);
			}
			
			return highestPriorityChildIndex;
		}
		
		void siftDown(uint index) 
		{
			while(hasChildren(index))
			{
				uint child = getHigherPriorityChildIndex(index);
				
				if(!comp(_storage[index], _storage[child])) {
					T temp = _storage[child];
					_storage[child] = _storage[index];
					_storage[index] = temp;
					
					index = child;
				} else {
					break;
				}
			}
		}
		
		void siftUp(uint index)
		{
			T nodeGoingUpData = _storage[index];
			
			while(hasParent(index)) {
				uint parentIndex = parent(index);
								
				if(!comp(_storage[parentIndex], nodeGoingUpData)) {
					_storage[index] = _storage[parentIndex];
					
					index = parentIndex;
				} else {
					break;
				}
			}
			
			_storage[index] = nodeGoingUpData;
		}
	
	private:
		std::vector<T> _storage;
		Comparator comp;
	
};

class Edge
{
	public:
		Edge() : x(0), y(0), cost(0) {}
		
		Edge(ulong first, ulong second, long c)
			:	x(first), y(second), cost(c)
		{}
	
	public:
		ulong x, y;
		long cost;
};

class EdgeIdComparator
{
	public:
		bool operator() (ulong first, ulong second) const
		{
			return ((*edges)[first]).cost < ((*edges)[second]).cost;
		}
		
		void setEdgeList(const std::vector<Edge> * edgeList) { edges = edgeList; }
		
	private:
		const std::vector<Edge> * edges;
};

class MinimumSpanningTree
{
	public:
		MinimumSpanningTree(std::vector<ulong> * adjacencyList, std::vector<Edge>& edgeList, ulong nVertices)
			:	numVertices(nVertices), cost(0), adjList(adjacencyList), edges(edgeList)
		{
			edgeVisited.resize(edges.size(), false);
			nodeInMst.resize(numVertices + 1, false);
			mstEdges.resize(numVertices - 1, 0);
			mstEdges.clear();
			
			cheapestEdge.getComparator().setEdgeList(&edges);
		}
		
	public:
		void execute()
		{
			/**
			 *	Init the cheapest edge heap by putting in all the edges
			 *	adjacent to the start node. Let the start node be 1.
			 */
			ulong startNode = 1;
			nodeInMst[startNode] = true;
			
			for(ulong i = 0; i < adjList[startNode].size(); i++)
			{
				ulong edgeId = adjList[startNode][i];
				
				edgeVisited[edgeId] = true;
				cheapestEdge.push(edgeId);
			}
			
			for(ulong i = 0; i < numVertices - 1; i++)
			{
				ulong edgeId;
				Edge minEdge;
				
				do {
					edgeId = cheapestEdge.pop();
					minEdge = edges[edgeId];;
				} while(nodeInMst[minEdge.x] && nodeInMst[minEdge.y]);
				
				ulong otherEnd 		= nodeInMst[minEdge.x] ? minEdge.y : minEdge.x;
				nodeInMst[otherEnd] = true;
				
				mstEdges.push_back(edgeId);
				cost += minEdge.cost;
				
				/**
				 *	Add more edges to our cheapest edge heap. Specifically, once
				 *	we added edge (x,y) to our MST, add all the non-visited edges
				 *	(y, w) to the heap.
				 */
				for(ulong j = 0; j < adjList[otherEnd].size(); j++)
				{
					ulong extraEdgeId 	= adjList[otherEnd][j];
					Edge edge 			= edges[extraEdgeId];
					ulong otherNode 	= (edge.x == otherEnd) ? edge.y : edge.x;
					
					if(!edgeVisited[extraEdgeId] && !nodeInMst[otherNode])
					{
						edgeVisited[extraEdgeId] = true;
						cheapestEdge.push(extraEdgeId);
					}
				}
			}
		}
				
		long getCost() const { return cost; }
		const std::vector<ulong>& getSolution() const { return mstEdges; }
		
	private:
		ulong numVertices;
		long cost;
		std::vector<ulong> * adjList;
		std::vector<Edge>& edges;
		std::vector<bool> edgeVisited;
		std::vector<bool> nodeInMst;
		std::vector<ulong> mstEdges;
		
		BinaryHeap<ulong, EdgeIdComparator> cheapestEdge;
};

int main(int argc, char * argv[]) 
{
	
	const char * inFile = "apm.in";
	const char * outFile = "apm.out";
	
	ifstream fin(inFile);
	ofstream fout(outFile);
	
	#ifndef NDEBUG
		if(!fin || !fout)
		{
			cerr << "Error opening one of \"" << inFile << "\" or \"" << outFile << "\"" << endl;
			return -1;
		}
	#endif
	
	/**
	 *	Read the data in.
	 */
	ulong numVertices, numEdges;
	fin >> numVertices >> numEdges;
	
	std::vector<Edge> edgeList;
	std::vector<ulong> adjList[numVertices + 1];
	
	edgeList.resize(numEdges);
	edgeList.clear();
	
	ulong x, y;
	long cost;
	ulong edgeId = 0;
	
	for(ulong i = 0; i < numEdges; i++)
	{
		fin >> x >> y >> cost;
		edgeList.push_back(Edge(x,y,cost));
		
		adjList[x].push_back(edgeId);
		adjList[y].push_back(edgeId);
		
		edgeId++;
	}
	
	/**
	 *	Solve the problem.
	 */
	MinimumSpanningTree mst(adjList, edgeList, numVertices);
	mst.execute();
	
	fout << mst.getCost() << "\n";
	fout << numVertices - 1 << "\n";
	
	const std::vector<ulong>& mstEdgeIds = mst.getSolution();
	
	for(std::vector<ulong>::const_iterator it = mstEdgeIds.begin();
		it != mstEdgeIds.end(); ++it)
	{
		Edge edge = edgeList[*it];
		fout << edge.x << " " << edge.y << "\n";
	}
	
	/**
	 *	Cleanup!
	 */
	fout.close();
	fin.close();
	
	return 0;
}