#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int NMAX = 2e5 + 5;
// in coada retin costul muchiei, primul nod si al doilea nod
priority_queue <pair < int, pair <int, int> > > coada;
int n, m;
int viz[NMAX];
vector <pair <int, int> > v[NMAX];
vector <pair <int, int> > sol;
long long sum;
void Prim()
{
	// marchez nodul de start ca vazut si adaug toate muchiile incidente cu nodul 1
	viz[1] = 1;
	for(int i = 0; i < v[1].size(); i++)
	{
		int son = v[1][i].first;
		int cost = v[1][i].second;
		coada.push(make_pair(-cost, make_pair(1, son)));
	}
	// In variabila 't' retin cate muchii am introdus in solutie
	// Cand 't' este egal cu n - 1 ma opresc
	int t = 0;
	while(t < n - 1)
	{
		// Cat timp muchia cu costul cel mai mic are vizat cel de al 2 lea nod sterg muchia
		while(viz[coada.top().second.second])
			coada.pop();
			t++;
		int nodCurent = coada.top().second.second;
		int cost = coada.top().first;
		int nodAnt = coada.top().second.first;
		sol.push_back(make_pair(nodAnt, nodCurent));
		sum += cost;
		// marchez nodul curent ca vizitat
		viz[nodCurent] = 1;
		//sterg muchia din coada
		coada.pop();
		for(int i = 0; i < v[nodCurent].size(); i++)
			if(!viz[v[nodCurent][i].first])
				coada.push(make_pair(-v[nodCurent][i].second, make_pair(nodCurent, v[nodCurent][i].first)));
				// adaug muchia in coada daca vecinul nodului curent (v[nodCurent][i].first) nu a fost vizitat
	}
}

int main()
{
	f >> n >> m;
	while(m--)
	{
		int x, y, c;
		f >> x >> y >> c;
		v[x].push_back(make_pair(y, c));
		v[y].push_back(make_pair(x, c));
	}
	Prim();
	g << -sum << "\n" << n - 1 << "\n" ;
	for(int i = 0; i < sol.size(); i++)
		g << sol[i].first << " " << sol[i].second << "\n";
}