#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > >V;
vector < pair < int, int > > v[200005];
int n, m, x, y, c, viz[200005];
struct Hugo_Boss
{
	int x, y;
}sol[200005];
struct graf
{
	int x, y, c;
}M[400005];
int prim(int nod)
{
	int i,j, cost, nodaux, b;
	cost = 0;
	b = 0;
	viz[nod] = 1;
	for (i = 1; i <= n - 1; i++)
	{
		for (j = 0; j < v[nod].size(); j++)
		{
			nodaux = v[nod][j].second;
			b = v[nod][j].first;
			if (!viz[nodaux]) V.push({ b,{nod,nodaux} });
		}
		while (viz[V.top().second.second]) 
			V.pop();
		cost += V.top().first;
		viz[V.top().second.second] = 1;
		sol[i].x = V.top().second.first;
		sol[i].y = V.top().second.second;
		V.pop();
	}
	return cost;
}
int main()
{
	int i;
	f >> n >> m;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y >> c;
		v[x].push_back({ c,y });
		v[y].push_back({ c,x });
	}
	g << prim(1) << '\n' << n - 1 << '\n';
	for (i = 1; i < n; i++)
		g << sol[i].x << " " << sol[i].y << '\n';
	return 0;
}