#include<fstream>
#include<string.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<array>
#include<deque>
#include<math.h>
#include<functional>
#include<unordered_set>
#include<set>
#include<iomanip>
#include<bitset>
using namespace std;
int n, m, i, j, k, c,x,y,point[200200],rang[200200];
struct edge
{
	int x;
	int y;
	int c;
}ed;
vector<edge>v;
vector<edge>::iterator it;
vector<pair<int, int>>ans;
vector<pair<int, int>>::iterator iter;
int rez;
bool comp(edge a, edge b)
{
	return a.c < b.c;
}
int find(int x, int y)
{
	int compx = x, aux, compy = y;
	while (point[x] != x)
		x = point[x];
	while (point[y] != y)
		y = point[y];
	while (point[compx] != compx)
	{
		aux = point[compx];
		point[compx] = x;
		compx = aux;
	}
	while (point[compy] != compy)
	{
		aux = point[compy];
		point[compy] = y;
		compy = aux;
	}
	return x == y;
}
void tie(int x, int y)
{
	while (point[x] != x)
		x = point[x];
	while (point[y] != y)
		y = point[y];
	if (rang[x] > rang[y])
		point[y] = x;
	else
		point[x] = y;
	if (rang[x] == rang[y])
		rang[y]++;
}
int main()
{
	//ifstream f("file.in");
	//ofstream g("file.out");
	ifstream f("apm.in");
	ofstream g("apm.out");
	f >> n >> m;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y >> c;
		ed.x = x;
		ed.y = y;
		ed.c = c;
		v.push_back(ed);
	}
	sort(v.begin(), v.end(), comp);
	it = v.begin();
	for (k = 1; k <= n; k++)
	{
		point[k] = k;
		rang[k] = 1;
	}
	int nr = 0;
	while (nr != n-1)
	{
		if (!(find(it->x, it->y)))
		{
			nr++;
			tie(it->x, it->y);
			rez += it->c;
			ans.push_back(make_pair(it->x, it->y));
		}
		if(it!=v.end())
			it++;
	}
	g << rez << '\n' << nr << '\n';
	iter = ans.begin();
	while (iter != ans.end())
	{
		g << iter->first << ' ' << iter->second << '\n';
		iter++;
	}
	return 0;
}