#include<fstream>
#include<utility>
#include<vector>
#include<queue>
using namespace std;
struct triplet
{
	int x, y, c;
}aux;
bool compara(triplet a, triplet b)
{
	return a.c < b.c;
}
vector<triplet> coada;
int queuesize;
triplet top()
{
	return coada[0];
}
int findsucc(int x)
{
	int min = 500000000,ret = 500000000;
	int vsize = coada.size();
	for (int i = x+1;( i <= x + queuesize && i < vsize ); i++)
	{
		if (coada[i].c < min)
		{
			min = coada[i].c;
			ret = i;
		}
	}
	return ret;
}
triplet c_t(int x, int y, int c)
{
	triplet z;
	z.x = x, z.y = y, z.c = c;
	return z;
}
void pop()
{
	int index = 0;
	int succesor = findsucc(0);
	triplet aux;
	coada[0] = coada[coada.size() - 1];
	int aux2 = coada.size();
	while (succesor < aux2 && compara(coada[succesor], coada[index]))
	{
		aux = coada[index];
		coada[index] = coada[succesor];
		coada[succesor] = aux;
		index *= queuesize;
		succesor=findsucc(succesor*queuesize);
	}
	coada.pop_back();
}
void push(triplet x)
{
	int index = coada.size() / queuesize;
	triplet aux;
	coada.push_back(x);
	int prev = coada.size() - 1;
	aux = coada[index];
	while (index >= 0 && compara(coada[prev], coada[index]))
	{
		aux = coada[index];
		coada[index] = coada[prev];
		coada[prev] = aux;
		if (index == 0)
			break;
		prev = index;
		if (index % queuesize == 0) index--;
		index /= queuesize;
	}
}
vector<pair<int, int> >v[200001];
queue<pair<int, int> > sol;
int n, m, i, x, y, c, nod;
long long sum;
bool viz[200001];
pair<int, int> aux2;
int main()
{
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	fin >> n >> m;
	queuesize = m / n;
	if (queuesize < 2)
		queuesize = 2;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> c;
		v[x].push_back(make_pair(y, c));
		v[y].push_back(make_pair(x, c));
		if (x == 1)
			push(c_t(x, y, c));
		if (y == 1)
			push(c_t(y, x, c));
	}
	viz[1] = 1;
	while (!coada.empty() && nod < n - 1)
	{
		aux = top();
		pop();
		while (viz[aux.y] == 1)
		{
			aux = top();
			pop();
		}
		viz[aux.y] = 1;
		sum += aux.c;
		nod++;
		sol.push(make_pair(aux.x, aux.y));
		for (vector<pair<int, int> >::iterator j = v[aux.y].begin(); j != v[aux.y].end(); j++)
		{
			if (viz[(*j).first] == 0)
				push(c_t(aux.y, (*j).first, (*j).second));
		}
	}
	fout << sum << '\n' << n - 1 << '\n';
	while (!sol.empty())
	{
		aux2 = sol.front();
		sol.pop();
		fout << aux2.first << ' ' << aux2.second << '\n';
	}
}