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

using namespace std;

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

const int N = 200005;

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

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

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

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

	priority_queue<pair<int, int>> heap;	// cost, nod
	heap.push({ 0, 1 });
	
	int CostTotal = 0;
	while (!heap.empty())
	{
		int nod = heap.top().second;
		int cost = heap.top().first;
		heap.pop();

		if (vizitat[nod])
		{
			continue;
		}

		vizitat[nod] = true;
		CostTotal -= cost;

		for (auto neigh : g[nod])
		{
			if (!vizitat[neigh.first] && neigh.second < CostMin[neigh.first])
			{
				heap.push({ -neigh.second, neigh.first });
				CostMin[neigh.first] = neigh.second;
				tata[neigh.first] = nod;
			}
		}
	}

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

/*

	

*/