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

using namespace std;

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

const int NMAX = 200005;
int n, m;
vector <pair<int,int>>G[NMAX];
vector <pair<int,int>> sol;

int cost;
bool viz[NMAX];

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

void prim(int fr)
{
	priority_queue <pair< int ,pair<int, int>> >pq;
	int noduri = 0;
	pq.push({ 0,{ fr,-1 } });
	while (noduri <= n && !pq.empty())
	{
		auto vf = pq.top();
		
		int costuri = -vf.first;
		int nod = vf.second.first;

		pq.pop();

		if(viz[nod])
			continue;

		viz[nod] = 1;
		cost += costuri;
		noduri++;
		sol.push_back({ vf.second });

		for (auto it : G[nod])
		{
			if (!viz[it.first])
				pq.push({ -it.second,{ it.first , nod } });
		}

	}
}
int main()
{
	read();
	prim(1);
	g << cost << '\n' << n - 1 << '\n';
	for (auto it : sol)
	{
		if (it.second != -1)
		{
			g << it.second << ' ' << it.first << '\n';
		}
	}
}