#include <fstream>
#include <vector>
#include <string>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int contor, noduri, legaturi, a, b, c, total, facut[200004], prima, final, copie[200004], afisat;

struct Vecin
{
	int poz, cost;
};

vector <Vecin> lista[200004];

struct Nod
{
	int a, b, c;
}heap[400004], nod;

void adauga(int a, int b, int c)
{
	contor++;
	int poz = contor;
	while (poz / 2 > 0 && heap[poz / 2].c > c)
	{
		heap[poz] = heap[poz / 2];
		poz /= 2;
	}

	heap[poz].a = a;
	heap[poz].b = b;
	heap[poz].c = c;
}

Nod scoate()
{
	Nod copie = heap[1];
	heap[1] = heap[contor];
	heap[contor].a = 0;
	heap[contor].b = 0;
	heap[contor].c = 0;

	contor--;
	int poz = 2;
	while (poz <= contor)
	{
		if (poz + 1 <= contor && heap[poz].c > heap[poz + 1].c)
			poz++;

		if (heap[poz / 2].c > heap[poz].c)
		{
			swap(heap[poz / 2], heap[poz]);
			poz *= 2;
		}
		else
			break;
	}
	return copie;
}

int main()
{
	cin >> noduri >> legaturi;
	for (int i = 1; i <= legaturi; i++)
	{
		cin >> a >> b >> c;
		lista[a].push_back({ b, c });
		lista[b].push_back({ a, c });
	}

	adauga(0, 1, 0);
	Nod nod;
	int cate = 1;
	while (cate <= noduri)
	{
		nod = scoate();
		while (facut[nod.b] == 1)
			nod = scoate();

		cate++;

		if (prima == 1)
		{	
			afisat++;
			copie[afisat] = nod.a;
			afisat++;
			copie[afisat] = nod.b;
			//sol = sol + to_string(nod.a) + ' ' + to_string(nod.b) + '\n';
			final++;
		}
		else
			prima = 1;
		for (int i = 0; i < lista[nod.b].size(); i++)
		{
			if (facut[lista[nod.b][i].poz] == 0)
			{
				adauga(nod.b, lista[nod.b][i].poz, lista[nod.b][i].cost);
			}
		}
		facut[nod.b] = 1;

		total += nod.c;
	}
	cout << total << '\n' << final << '\n';
	for (int i = 1; i <= afisat; i+=2)
	{
		cout << copie[i] << ' ' << copie[i + 1] << '\n';
	}
}