#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair <int, int> > d[200001];
vector<pair<pair< int,int >,int > > g;
vector<pair< int, int > > r;
int gasit[200001],dr;
bool c(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
{
	if (a.first.second > b.first.second)
	{ 
		return 1;
	}
	return 0;
}
int main()
{
	ifstream in("apm.in");
	ofstream out("apm.out");
	int i, n, m, x, y,z,tot=1;
	gasit[1] = 1;
	in >> n;
	in >> m;
	for (i = 1; i <= m; i++)
	{
		in >> x;
		in >> y;
		in >> z;
		d[x].push_back(make_pair(y, z));
		d[y].push_back(make_pair(x, z));
	}
	for (i = 0; i < d[1].size(); i++)
	{
		g.push_back(make_pair(d[1][i],1));
	}
	make_heap(g.begin(), g.end(), c);
	while (tot<n)
	{
		x = g[0].second;
		y = g[0].first.first;
		z = g[0].first.second;
		pop_heap(g.begin(), g.end(), c);
		g.pop_back();
		if (gasit[y] == 0)
		{
			gasit[y] = 1;
			tot++;
			dr += z;
			r.push_back(make_pair(x, y));
			for (i = 0; i < d[y].size(); i++)
			{
				g.push_back(make_pair(d[y][i], y));
				push_heap(g.begin(), g.end(), c);
			}
		}
	}
	out << dr << "\n"<<n-1<<"\n";
	for (i = 0; i < r.size(); i++)
	{
		out << r[i].first << " " << r[i].second << "\n";
	}
}