#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <limits.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int N = 200005, INF = INT_MAX;

vector<pair<int, int>> g[N];
bool vizitat[N];
int CostMin[N];
int tata[N];

int main()
{
	int n, m;
	fin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		fin >> a >> b >> c;
		g[a].push_back({ b, c });
		g[b].push_back({ a, c });
	}

	for (int i = 2; i <= n; i++)
	{
		CostMin[i] = INF;
	}

	set<pair<int, int>> heap;		// cost, spre nod
	heap.insert({ 0, 1 });

	int CostTotal = 0;
	while (!heap.empty())
	{

		int nod = heap.begin()->second;
		CostTotal += heap.begin()->first;
		heap.erase(heap.begin());
		vizitat[nod] = true;

		for (auto neigh : g[nod])
		{
			int NodVecin = neigh.first;
			int CostVecin = neigh.second;

			if (!vizitat[NodVecin] && CostVecin < CostMin[NodVecin])
			{
				if (CostMin[NodVecin] != INF)
				{
					heap.erase(heap.find({ CostMin[NodVecin], NodVecin }));
				}

				heap.insert({ CostVecin, NodVecin });
				CostMin[NodVecin] = CostVecin;
				tata[NodVecin] = nod;
			}
		}
	}

	fout << CostTotal << '\n' << n - 1 << '\n';
	for (int i = 2; i <= n; i++)
	{
		fout << i << ' ' << tata[i] << '\n';
	}
}