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

//Definitii
#define cost first
#define to second

//Constante
const int MAX_SIZE = (int)2e5+1;
const int oo = (int)15e8;

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

int n, m;
int costTotal;

bool isInArbore[MAX_SIZE];

vector<int> arbore;
vector<int>::iterator it, end;
vector<pair<int,int> > raspuns;
vector<pair<int,int> >::iterator pit, rend;

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > graf[MAX_SIZE];

//Main
int main()
{
	in >> n >> m;
	int cFrom, cTo, cCost;
	for(int i=1 ; i<=m ; ++i)
	{
		in >> cFrom >> cTo >> cCost;
		graf[cFrom].push(make_pair(cCost, cTo));
		graf[cTo].push(make_pair(cCost, cFrom));
	}
	
	arbore.push_back(1);
	isInArbore[1] = true;
	
	for(int i=1 ; i<n ; ++i)
	{
		pair<int,int> minim = make_pair(oo, oo);
		int pozMin;
		end = arbore.end();
		for(it=arbore.begin() ; it!=end ; ++it)
		{
			while(!graf[*it].empty() && isInArbore[graf[*it].top().to])
				graf[*it].pop();
			if(graf[*it].empty())
				continue;
			if(graf[*it].top() < minim)
				minim = graf[*it].top(), pozMin = *it;
		}
		
		arbore.push_back(minim.to);
		isInArbore[minim.to] = true;
		graf[pozMin].pop();
		costTotal += minim.cost;
		raspuns.push_back(make_pair(pozMin, minim.to));
	}
	
	out << costTotal << '\n' << n-1;
	
	rend = raspuns.end();
	for(pit = raspuns.begin() ; pit!=rend ; ++pit)
		out << '\n' << pit-> first << ' ' << pit->second;
	
	in.close();
	out.close();
	return 0;
}