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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int nmax = 200005;
int n, m;
vector<pair<int, int>>G[nmax];
bool viz[nmax];
int nodes;
int costTotal;
vector<pair<int, int>>edges;

void read()
{
	f >> n >> m;
	int x, y, c;
	for (int i = 1; i <= m; i++)
	{
		f >> x >> y >> c;
		G[x].push_back({ y, c });
		G[y].push_back({ x, c });
	}
}

void prim()
{
	priority_queue<pair<int, pair<int,int>>>pq;
	pq.push({ 0, {1, -1} });
	while (!pq.empty() && nodes <= n)
	{
		auto varf = pq.top();
		pq.pop();

		int cost = varf.first;
		int nod = varf.second.first;

		if (viz[nod])
		{
			continue;
		}

		nodes++;

		viz[nod]++;

		costTotal -= cost;

		edges.push_back(varf.second);

		for (auto it : G[nod])
		{
			if (!viz[it.first])
			{
				pq.push({ -it.second, {it.first, nod} });
			}
		}
	}
}
void print() {
	g << costTotal << "\n";
	g << n - 1 << "\n";
	for (auto edge : edges) 
	{
		if (edge.second == -1) 
		{
			continue;
		}
		g << edge.first << " " << edge.second << "\n";
	}
}
int main()
{
	read();
	prim();
	print();
}