#include<fstream>
#include<utility>
#include<vector>
#include<queue>
#include<ctime>
#include<iostream>
using namespace std;
struct triplet
{
	int x, y, c;
} aux;
triplet c_t(int x, int y, int c)
{
	triplet z;
	z.x = x, z.y = y, z.c = c;
	return z;
}
class compare_q
{
public:
	bool operator() (triplet a, triplet b)
	{
		return a.c > b.c;
	}
};
vector<pair<int, int> >v[200001];
priority_queue<triplet, vector<triplet>, compare_q> q;
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;
	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)
			q.push(c_t(x, y, c));
		if (y == 1)
			q.push(c_t(y, x, c));
	}
	viz[1] = 1;
	while (!q.empty() && nod < n - 1)
	{
		aux = q.top();
		q.pop();
		while (viz[aux.y] == 1)
		{
			aux = q.top();
			q.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)
				q.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';
	}
}