#include<fstream>
#include<utility>
#include<vector>
#include<queue>
#include<ctime>
#include<iostream>
#include<cassert>
#include<string>
using namespace std;
struct triplet
{
	int x, y, c;
};
bool compara(triplet a, triplet b)
{
	return a.c <= b.c;
}
vector<triplet> coada;
int numberOfChildren;
triplet c_t(int x, int y, int c)
{
	triplet z;
	z.x = x, z.y = y, z.c = c;
	return z;
}
triplet top()
{
	if (coada.size() <= 0)
		return c_t(1, 1, -1000000);
	return coada[0];
}
int findsucc(int x)
{
	int vsize = coada.size();
	x = x*numberOfChildren;
	int  ret = x + 1;
	if (x + 1 < vsize)
	{
		triplet min = coada[x + 1];
		for (int i = x + 2; (i <= x + numberOfChildren && i < vsize); i++)
		{
			if (compara(coada[i], min))
			{
				min = coada[i];
				ret = i;
			}
		}
	}
	else
	{
		ret = 5000000;
	}
	return ret;
}

void pop()
{
	int index = 0;
	int succesor;
	coada[0] = coada.back();
	coada.pop_back();
	int size = coada.size();
	succesor = findsucc(0);
	while (succesor < size && compara(coada[succesor], coada[index]))
	{
		swap(coada[index], coada[succesor]);

		index = succesor;
		succesor = findsucc(index);
	}
}
void push(triplet x)
{
	int father;
	coada.push_back(x);
	int child = coada.size() - 1;
	father = max((child - 1),0)/ numberOfChildren;
	while (father >= 0 && compara(coada[child], coada[father]))
	{
		swap(coada[father], coada[child]);
		if (father == 0)
			break;
		child = father;
		father = (father - 1) / numberOfChildren;
	}
}
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()
{
	triplet aux;
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	fin >> n >> m;
	numberOfChildren = m / n;
	if (numberOfChildren < 2)
		numberOfChildren = 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';
	}
}