#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define INF 10000000

using namespace std;

int n, m, costTotal;
vector<bool> vizitat;
vector<int> cost;
vector<vector<pair<int, int>>> vecini;
vector<int> tata;

class myComparator
{		
public:
    int operator() (const int p1, const int p2)
    {
        return cost[p1] > cost[p2];
    }
};

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

priority_queue <int, vector<int>, myComparator> coada; 


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

	f >> n >> m;

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

	for(int i = 0; i < m; i++)
	{
		int nod1, nod2, c;

		f >> nod1 >> nod2 >> c;

		vecini[nod1].push_back(make_pair(nod2, c));
		vecini[nod2].push_back(make_pair(nod1, c));
	}
}

void prim()
{
	int vecin, costVecin, nodCurent;

	cost[1] = 0;
	tata[1] = -1;

	coada.push(1);

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

		if(!vizitat[nodCurent])
		{
			costTotal += cost[nodCurent];
			vizitat[nodCurent] = true;
		}
		else continue;

		for(auto pereche : vecini[nodCurent])
		{
			vecin = pereche.first;
			if(!vizitat[vecin])
			{
				costVecin = pereche.second;

				if(costVecin < cost[vecin])
				{
					cost[vecin] = costVecin;
					coada.push(vecin);
					tata[vecin] = nodCurent;
				}
			}	
		}	
	}
}

void afisare()
{
	ofstream g("apm.out");
	g << costTotal << endl;
	g << n - 1 << endl;
	for(int i = n; i >= 1; i--)
	{
		int nod = i;
		while(tata[nod] != -1)
		{
			g << tata[nod] << ' ' << nod << endl;
			int nodAux = nod;
			nod = tata[nod];
			tata[nodAux] =  -1;
		}
	}
}

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

	return 0;
}