// Include
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

// Definitii
#define pb push_back
#define mp make_pair

#define edge_t pair<int, int>
#define path_t pair<int, edge_t>
#define cost first
#define edge second 

// Constante
const int sz = (int)2e5+1;

// Functii
int getRoot(int node);

// Variabile
ifstream in("apm.in");
ofstream out("apm.out");

int nodes, edges;
int totalCost;
int father[sz];

vector<edge_t> answer;

priority_queue< path_t, vector<path_t>, greater<path_t> > heap;

// Main
int main()
{
	in >> nodes >> edges;
	
	int rFrom, rTo, rCost;
	while(edges--)
	{
		in >> rFrom >> rTo >> rCost;
		heap.push(mp(rCost, mp(rFrom, rTo)));
	}
	
	while(!heap.empty())
	{
		path_t current = heap.top();
		heap.pop();
		
		int node1 = current.edge.first;
		int node2 = current.edge.second;
		int root1 = getRoot(node1);
		int root2 = getRoot(node2);
		
		if(root1 == root2)
			continue;
		
		totalCost += current.cost;
		answer.push_back(current.edge);
		
		father[root2] = root1;
	}
	
	out << totalCost << '\n';
	out << nodes-1 << '\n';
	
	vector<edge_t>::iterator it, end=answer.end();
	for(it=answer.begin() ; it!=end ; ++it)
		out << it->first << ' ' << it->second << '\n';
	
	in.close();
	out.close();
	return 0;
}


int getRoot(int node)
{	return father[node]? father[node] = getRoot(father[node]) : node;	}