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

using namespace std;

struct Muchie
{
	int nod1, nod2, cost;
};

class myComparator
{		
public:
    int operator() (const Muchie& m1, const Muchie& m2)
    {
        return m1.cost > m2.cost;
    }	
};

int n, m, costTotal;
vector<vector<pair<int, int>>> vecini;
vector<bool> vizitat;
vector<Muchie> solutie;
priority_queue <Muchie, vector<Muchie>, myComparator> coada; 

void citire()
{
	ifstream f("apm.in");

	int nod1, nod2, cost;
	
	f >> n >> m;

	vizitat.resize(n + 1, false);
	vecini.resize(n + 1);

	for(int i = 0; i < m; i++)
	{
		f >> nod1 >> nod2 >> cost;
		vecini[nod1].push_back({nod2, cost});	
		vecini[nod2].push_back(make_pair(nod1, cost));	
	}
}

void prim()
{
	vizitat[1] = true;
	
	for(int i = 0; i < vecini[1].size(); i++)
	{
		int vecin = vecini[1][i].first;
		int cost = vecini[1][i].second;
		coada.push({1, vecin, cost});
	}

	while(!coada.empty())
	{
		Muchie muchieCurenta = coada.top();
		coada.pop();

		int nod1 = muchieCurenta.nod1;
		int nod2 = muchieCurenta.nod2;

		if(vizitat[nod2])
			continue;

		solutie.push_back(muchieCurenta);
		vizitat[nod2] = true;
		costTotal += muchieCurenta.cost;

		for(int i = 0; i < vecini[nod2].size(); i++)
		{
			int vecin = vecini[nod2][i].first;
			int cost = vecini[nod2][i].second;
			coada.push({nod2, vecin, cost});
		}
	}
}

void afisare()
{
	ofstream g("apm.out");

	g << costTotal << endl;
	g << n - 1 << endl;

	for(int i = 0; i < solutie.size(); i++)
		g << solutie[i].nod1 << ' ' << solutie[i].nod2 << endl;
}

int main()
{
	citire();
	prim();
	afisare();

	return 0;
}