#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <string.h>

#define INF 	0x17D7841
#define MAXN	200001

using namespace std;

typedef unsigned int uint32;
typedef vector<vector<pair<uint32,short> > > Graph;

class CHeap
{
private:
	uint32 size;
	vector<uint32> vIndexes;
	vector<pair<int,uint32> > vHeap;	// key - value
	
	inline void swap(const uint32 first, const uint32 second)
	{
		vIndexes[vHeap[first].second] = second;
		vIndexes[vHeap[second].second] = first;
		
		pair<int,uint32> aux;
		
		aux = vHeap[first];
		vHeap[first] = vHeap[second];
		vHeap[second] = aux;
	}
	
	void siftUp(int index)
	{
		int parent=(index-1-!(index%2))>>1;
		while (parent>=0 && vHeap[index].first<vHeap[parent].first)
		{
			swap(parent,index);
			index = parent;
			parent = (index-1-!(index%2))>>1;
		}
	}
	
	void siftDown(int index)
	{
		int child1,child2;
		bool ord = true;
		
		child1 = (index<<1)+1;
		child2 = (index+1)<<1;
		
		while (ord && child1<size)
		{
			ord = false;
			if (child2<size)
			{
				if (vHeap[child1].first<vHeap[child2].first)
				{
					if (vHeap[child1]<vHeap[index])
					{
						swap(child1,index);
						index = child1;
						ord = true;
					}
				}
				else if (vHeap[child2].first<vHeap[index].first)
				{
					swap(child2,index);
					index = child2;
					ord = true;
				}
			}
			else if (vHeap[child1].first<vHeap[index].first)
			{
				swap(child1,index);
				index = child1;
				ord = true;
			}
			
			child1 = (index<<1)+1;
			child2 = (index+1)<<1;
		}
	}
public:

	CHeap() : size(0)
	{}

	void insert(const pair<int,uint32>& val)
	{
		vHeap.push_back(val);
		vIndexes.push_back(size++);
		siftUp(size-1);
	}
	
	inline void modify(const int pos, const pair<int,uint32>& val)
	{
		vHeap[pos]=val;
		siftUp(pos);
	}
	
	inline void remove(const int pos)
	{
		swap(pos,--size);
		vHeap.pop_back();
		siftDown(pos);
	}
	
	inline const pair<int,uint32>& getElement(const int pos) const
	{
		return vHeap[pos];
	}
	
	inline int getPos(const int index) const
	{
		return vIndexes[index];
	}
	
	inline bool empty() const
	{
		return (size==0);
	}
	
	void print()
	{
		for (unsigned int i=0; i<vHeap.size(); ++i)
		{
			cout<<"("<<vHeap[i].first<<" "<<vHeap[i].second<<") ";
		}
		cout<<endl;
	}
};

struct Edge
{
	Edge() {}
	Edge(const int s,
		const int d) : src(s), dest(d)
	{}

	int src, dest;
};

bitset<MAXN> used;
int edges[MAXN];

int Prim(Graph& graph, const int n, vector<Edge>& output)
{
	int src=1;
	int nodesAdded=1;
	int totalCost=0;
	CHeap heap;
	used.reset();
	
	used[src] = true;
	heap.insert(make_pair(INF,0));
	for (int i=1; i<=n; ++i)
	{
		heap.insert(make_pair(INF,i));
	}
	
	for (int i=0; i<graph[src].size(); ++i)
	{
		//heap.insert(make_pair(graph[src][i].second, graph[src][i].first)); // key (cost) - value (nod index)
		heap.modify(heap.getPos(graph[src][i].first),make_pair(graph[src][i].second,graph[src][i].first));
		edges[graph[src][i].first] = src;
	}
	
	while (nodesAdded < n)
	{
		const pair<int,uint32> node = heap.getElement(0);
		heap.remove(0);
		
		used[node.second] = true;
		output.push_back(Edge(node.second, edges[node.second]));
		
		//cout << "Chosen node = " << node.second << endl;
		
		totalCost += node.first;
		//cout << "Total cost = " << totalCost << endl;
		nodesAdded++;
		
		for (vector<pair<uint32,short> >::iterator it=graph[node.second].begin(); it!=graph[node.second].end(); ++it)
		{
			if (!used[it->first])
			{
				const pair<int,uint32> candidate = heap.getElement(heap.getPos(it->first));
				
				if (candidate.first > it->second)
				{
					//cout << "Modifying node = " << it->first << endl;
					heap.modify(heap.getPos(it->first),make_pair(it->second,it->first));
					edges[it->first] = node.second;
				}
			}
		}
		//cout << endl;
	}
	
	return totalCost;
}

int main()
{
	int n,m;
	Graph graph;
	vector<Edge> output;
	fstream fin("apm.in", fstream::in);
	fstream fout("apm.out", fstream::out);
	
	
	fin >> n >> m;
	//cout << n << " " << m << endl;
	
	graph.resize(n+2);
	
	for (int i=0; i<m; ++i)
	{
		int x, y;
		short c;
		
		fin >> x >> y >> c;
		
		graph[x].push_back(make_pair(y, c));
		graph[y].push_back(make_pair(x, c));
	}
	
	/*for (int i=1; i<=n; ++i)
	{
		cout << i << ": ";
		
		for (int j=0; j<graph[i].size(); ++j)
		{
			cout << "(" << graph[i][j].first << "," << graph[i][j].second << ") ";
		}
		cout << endl;
	}*/
	
	fout << Prim(graph, n, output) << "\n";
	fout << output.size() << "\n";
	
	for (int i=0; i<output.size(); ++i)
	{
		fout << output[i].src << " " << output[i].dest << "\n";
	}
	
	fin.close();
	fout.close();
}