#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

void Kruskal();
int Find(int x);
void Union(int x, int y);

struct edge
{
	int x, y, c;
};
struct ev
{
	int x, y;
	ev() {}
	ev(int _x, int _y)
	{
		x = _x, y = _y;
	}
};
bool cmp(const edge& e1, const edge& e2)
{
	return e1.c <= e2.c;
}

int n, m, t[200001], s[200001], cost;
edge e[400001];
vector<ev> h;

int main()
{
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	fin >> n >> m;
	for (int i = 1; i <= m; ++i)
		fin >> e[i].x >> e[i].y >> e[i].c;
	Kruskal();
	fout << cost << '\n' << n - 1 << '\n';
	for (int i = 0; i < h.size(); ++i)
		fout << h[i].x << ' ' << h[i].y << '\n';
}

void Kruskal()
{
	sort(e + 1, e + m + 1, cmp);
	for (int i = 1; i <= n; ++i)
		t[i] = i, s[i] = 1;
	int cc = n, i = 1;
	while (cc != 1)
	{
		if (Find(e[i].x) != Find(e[i].y))
		{
			cost += e[i].c;
			Union(Find(e[i].x), Find(e[i].y));
			h.push_back(ev(e[i].x, e[i].y));
			--cc;
		}
		++i;
	}
}

int Find(int x)
{
	if (t[x] != x) t[x] = Find(t[x]);
	return t[x];
}
void Union(int x, int y)
{
	if (s[x] > s[y])
		t[y] = x;
	else 
	{
		t[x] = y;
		if (s[x] == s[y])
			++s[y];
	}
}