#define _CRT_SECURE_NO_WARNINGS
// FIRST (... that compiles) UPLOAD, MESSY CODE

#include <cstdio>
#include <algorithm>
#include <vector>
#include <conio.h>

using namespace std;

//qqq // no 'key' typename needed if u want a heap with some special structure, just overload the '<' operator
template <typename Content>
class SexyNode
{
	Content _content;
	unsigned int _id;
	unsigned int _rank;
	bool _marked;

	SexyNode<Content>* _previous;
	SexyNode<Content>* _next;
	SexyNode<Content>* _child; // first-born
	SexyNode<Content>* _parent;

	SexyNode();
	SexyNode(Content, unsigned int);
	~SexyNode();

	Content getContent();
	void insert(SexyNode<Content>*);
	void insertChild(SexyNode<Content>*);
	void remove();
	void removeChild(SexyNode<Content>*);

	template <typename> friend class SexyHeap;
};

template <typename Content>
class SexyHeap
{
	typedef SexyNode<Content>* PSexyNode;

	PSexyNode _minroot;
	unsigned int _count;
	unsigned int _maxrank;
	PSexyNode insertNode(PSexyNode);
	void merge(const SexyNode<Content>&);

public:
	SexyHeap();
	~SexyHeap();
	unsigned int getMinId();
	Content getMin();
	PSexyNode insert(Content, unsigned int);
	void removeMinimum();
	void decreaseNode(PSexyNode, Content);
	void remove(PSexyNode, Content);
	bool isHeapEmpty();
};

// LAME OOP yukk ...
class SexyGraphNode
{
public:
	unsigned int _value;
	int _cost;
	unsigned int _id;
	SexyGraphNode* _next;

	SexyGraphNode(){};
	~SexyGraphNode(){};

	friend class SexyGraphAdjacency;
};

class SexyGraphAdjacency
{
public:
	vector<unsigned> _serializededges[2];
	vector<SexyGraphNode*> _nodes;
	unsigned int _nodecount;
	unsigned int _edgecount;

	SexyGraphAdjacency();
	~SexyGraphAdjacency();
	void LoadEdges(char*);
};

// main
int main()
{
	char filename[] = "prim.in";
	freopen("prim.out", "wt", stdout);
	SexyGraphAdjacency sga;
	SexyHeap<int> sh;
	vector<unsigned int> result;
	int resultcost;

	sga.LoadEdges(filename);
//	unsigned int inf = (unsigned int)(1 << 31);
	//for (int i = 1; i < sga._nodecount; ++i)
	//{
	//	SexyGraphNode* asdf = sga._nodes[i];
	//	while (asdf)
	//	{
	//		printf("%d > %d: %u\n", i, asdf->_value, asdf->_cost);
	//		asdf = asdf->_next;
	//	}
	//}
	//printf("%u\n", sga._edgecount);
	for (unsigned int i = 0; i < sga._edgecount; ++i)
	{
		//printf("%u: %d <-> %d\n", i, sga._serializededges[0][i], sga._serializededges[1][i]);
	}

	unsigned int startnode = 1;
	SexyGraphNode* tempnode;

	resultcost = 0;
	// add initial edges (edges connected to the startnode)
	tempnode = sga._nodes[startnode];
	while (tempnode)
	{
		sh.insert(tempnode->_cost, tempnode->_id);
		tempnode = tempnode->_next;
	}
	//printf("%d\n", sh.getMin());
	//printf("%d\n", sh.getMinId());
	//sh.removeMinimum();
	//printf("%d\n", sh.getMin());
	//printf("%d\n", sh.getMinId());

	vector<bool> isintree(sga._nodecount + 1, false);
	unsigned int k = 1; // 1 node already in the tree
	isintree[startnode] = true;
	while (k < sga._nodecount && !sh.isHeapEmpty())
	{
		unsigned int pottentialnode = sga._serializededges[1][sh.getMinId()];

		//printf("minpot: %d, potential node: %u, id: %d\n", sh.getMin(), pottentialnode, sh.getMinId());
		// is the node in the tree already?
		bool badnode = false;
		for (unsigned int i = 0; i < k; ++i)
		{
			if (isintree[pottentialnode])
			{
				sh.removeMinimum();
				badnode = true;
				//printf("bad\n");
				break;
			}
		}

		//while (!sh.isHeapEmpty())
		//{
		//	printf("minnn: %d\n", sh.getMin());
		//	sh.removeMinimum();
		//}

		if (badnode)
		{
			continue;
		}
		// goodnode!
		else
		{
			//printf("GOOD: %d\n", pottentialnode);
			result.push_back(sh.getMinId());
			isintree[pottentialnode] = true;
			resultcost += sh.getMin();
			sh.removeMinimum();
			//add the pottentialnodes neighbours
			tempnode = sga._nodes[pottentialnode];
			while (tempnode)
			{
				//printf("add:%d\n", tempnode->_cost);
				sh.insert(tempnode->_cost, tempnode->_id);
				tempnode = tempnode->_next;
			}
			++k;
		}
	}

	--k;
	if (k != sga._nodecount - 1)
	{
		printf("fail %d\n", k);
	}
	else
	{
		printf("%d\n%d\n", resultcost, k);
		for (unsigned int i = 0; i < k; ++i)
		{
			printf("%d %d\n", sga._serializededges[0][result[i]], sga._serializededges[1][result[i]]);
		}
	}
	//_getch();
}

// SexyNode
template <typename Content>
SexyNode<Content>::SexyNode()
{
}

template <typename Content>
SexyNode<Content>::SexyNode(Content c, unsigned int id): _content(c)
{
	_content = c;
	_id = id;
	_rank = 0;
	_marked = 0;

	_previous = _next = this;
	_child = 0;
	_parent = 0;
}

template <typename Content>
SexyNode<Content>::~SexyNode()
{
}

template <typename Content>
Content SexyNode<Content>::getContent()
{
	return _content;
}

template <typename Content>
void SexyNode<Content>::insert(SexyNode<Content>* newnode)
{
	if (!newnode) return; // ?!

	this->_next->_previous = newnode->_previous;
	newnode->_previous->_next = this->_next;
	this->_next = newnode;
	newnode->_previous = this;
}

template <typename Content>
void SexyNode<Content>::insertChild(SexyNode<Content>* newnode)
{
	if (!_child)
		_child = newnode;
	else
		_child->insert(newnode);
	newnode->_parent = this;
	newnode->_marked = 0;
	++_rank;
}

template <typename Content>
void SexyNode<Content>::remove()
{
	this->_previous->_next = this->_next;
	this->_next->_previous = this->_previous;
	this->_next = this->_previous = this;
}

template <typename Content>
void SexyNode<Content>::removeChild(SexyNode<Content>* oldnode)
{
	if (oldnode->_parent != this)
		return;
	if (oldnode->_next == oldnode)
	{
		if (_child != oldnode)
		{
			return;
		}
		_child = 0;
	}
	else
	{
		if (_child == oldnode)
			_child = oldnode->_next;
		oldnode->remove();
	}

	oldnode->_parent = 0;
	oldnode->_marked = 0;
	--_rank;
}

//template <typename Content>
//ostream& operator<< (ostream& out, const SexyNode<Content>& node)
//{
//	return (out << "Data: " << node._content << endl
//		<< "Has child: " <<  _child : "yes" ? "no" << endl
//		<< "Has parent: " << _parent : "yes" ? "no" << endl << endl);
//}

// SexyHeap
template <typename Content>
SexyHeap<Content>::SexyHeap(): _minroot()
{
	_minroot = 0;
	_count = 0;
	_maxrank = 0;
}

template <typename Content>
SexyHeap<Content>::~SexyHeap()
{
}

template <typename Content>
SexyNode<Content>* SexyHeap<Content>::insertNode(PSexyNode newnode)
{
	if (!_minroot)
	{
		_minroot = newnode;
	}
	else
	{
		_minroot->insert(newnode);
		if (newnode->getContent() < _minroot->getContent())
			_minroot = newnode;
	}

	return newnode;
}

template <typename Content>
unsigned int SexyHeap<Content>::getMinId()
{
	if (_minroot)
		return _minroot->_id;
	return 0; // f&*(ed
}

template <typename Content>
Content SexyHeap<Content>::getMin()
{
	if (_minroot)
		return _minroot->getContent();
	else
		return (Content) (1 << 31); // f&*(ed
}

template <typename Content>
void SexyHeap<Content>::merge(const SexyNode<Content>& second)
{
	_minroot->insert(second._minroot);
	if (!_minroot || (second._minroot && second._minroot->GetContent < _minroot->GetContent()))
	{
		_minroot = second._minroot;
	}

	_count += second._count;
}

template <typename Content>
SexyNode<Content>* SexyHeap<Content>::insert(Content newcontent, unsigned int id)
{
	++_count;

	return insertNode(new SexyNode<Content>(newcontent, id));
}

template <typename Content>
void SexyHeap<Content>::removeMinimum()
{
	if (!_minroot)
		return;

	--_count;

	// all child >> root
	if (_minroot->_child)
	{
		PSexyNode tempnode = _minroot->_child;
		do
		{
			tempnode->_parent = 0;
			tempnode = tempnode->_next;
		} while (tempnode != _minroot->_child);
		_minroot->_child = 0;
		_minroot->insert(tempnode);
	}

	// last element
	if (_minroot->_next == _minroot)
	{
		if (_count)
			return; // something is f&*ed up
		_minroot = 0;
		return;
	}

	// merge same-rank roots
	vector<PSexyNode> samerankroots(_maxrank + 1);
	fill(samerankroots.begin(), samerankroots.end(), (PSexyNode) 0);
	_maxrank = 0;
	PSexyNode currentnode = _minroot->_next;
	unsigned int currentrank;

	do 
	{
		currentrank = currentnode->_rank;

		PSexyNode currentnodelvl2 = currentnode;
		currentnode = currentnode->_next;
		while (samerankroots[currentrank]) // qqq // merge the two roots with the same rank
		{
			PSexyNode second =  samerankroots[currentrank];
			if (second->getContent() < currentnodelvl2->getContent())
				swap(second, currentnodelvl2);
			second->remove();
			currentnodelvl2->insertChild(second);
			samerankroots[currentrank++] = 0;
			if (currentrank >= samerankroots.size())
				samerankroots.push_back((PSexyNode) 0);
		}
		// keep the current root as the first of its rank in the samerankroots array
		samerankroots[currentrank] = currentnodelvl2;
	} while (currentnode != _minroot);

	// remove the current root, and calculate the new rootmin
	delete _minroot;
	_minroot = 0;

	unsigned int newmaxrank = 0;

	for (unsigned int r = 0; r < samerankroots.size(); ++r)
	{
		if (samerankroots[r])
		{
			samerankroots[r]->_next = samerankroots[r]->_previous = samerankroots[r];
			insertNode(samerankroots[r]);
			if (r > newmaxrank)
				newmaxrank = r;
		}
	}
	_maxrank = newmaxrank;
}

template <typename Content>
void SexyHeap<Content>::decreaseNode(PSexyNode changenode, Content newcontent) {
	if (!(newcontent < changenode->getContent()))
		return; // f*&ed up ...

	changenode->_content = newcontent;

	// agressiv or not
	PSexyNode parent = changenode->_parent;
	if (!parent)
	{
		if (newcontent < _minroot->getContent())
			_minroot = changenode;
		return;
	}
	else
		if (parent->getContent() < newcontent || parent->getContent() == newcontent)
			return; // heap healthy

	for (;;)
	{
		parent->removeChild(changenode);
		insertNode(changenode);

		if (!parent->_parent)
			break;
		else if (!parent->_marked)
		{
			parent->_marked = 1;
			break;
		}
		else
		{
			changenode = parent;
			parent = parent->_parent;
			continue;
		}
	}
}

template <typename Content>
void SexyHeap<Content>::remove(PSexyNode oldnode, Content minusinf)
{
	if (!(minusinf < _minroot))
		return; // f*(&ed up

	decreaseNode(oldnode, minusinf);
	removeMinimum();
}

template <typename Content>
bool SexyHeap<Content>::isHeapEmpty()
{
	return (_count ? false : true);
}
// SexyGraphAdjacency
SexyGraphAdjacency::SexyGraphAdjacency()
{
}

SexyGraphAdjacency::~SexyGraphAdjacency()
{
}

void SexyGraphAdjacency::LoadEdges(char* from)
{
	freopen(from, "rt", stdin);

	scanf("%u %d", &_nodecount, &_edgecount);
	_nodes = vector<SexyGraphNode*>(_nodecount + 1, 0);
	_serializededges[0] = vector<unsigned int>(2 * (_edgecount + 1), 0);
	_serializededges[1] = vector<unsigned int>(2 * (_edgecount + 1), 0);

	for (unsigned int i = 0; i < _edgecount; ++i)
	{
		unsigned int from, to;
		int cost;
		SexyGraphNode* tempnode = new SexyGraphNode;
		SexyGraphNode* tempnode2 = new SexyGraphNode;

		scanf("%u %u %u", &from, &to, &cost);

		tempnode->_cost = cost;
		tempnode->_value = to;
		tempnode->_next = _nodes[from];
		tempnode->_id = i;
		_nodes[from] = tempnode;

		tempnode2->_cost = cost;
		tempnode2->_value = from;
		tempnode2->_next = _nodes[to];
		tempnode2->_id = _edgecount + i;
		_nodes[to] = tempnode2;

		_serializededges[0][i] = from;
		_serializededges[1][i] = to;
		_serializededges[0][_edgecount + i] = to;
		_serializededges[1][_edgecount + i] = from;
	}
}