#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;
	}
};

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

bool cmp(const int& e1, const int& e2)
{
	return e[e1].c < e[e2].c;
}

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;
		in[i] = i;
	}
	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(in + 1, in + m + 1, cmp);
	for (int i = 1; i <= n; ++i)
		t[i] = i, s[i] = 1;
	int cc = n, i = 1;
	while (cc != 1)
	{
		int ax1 = Find(e[in[i]].x), ax2 = Find(e[in[i]].y);
		if (ax1 != ax2)
		{
			cost += e[in[i]].c;
			Union(ax1, ax2);
			h.push_back(ev(e[in[i]].x, e[in[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];
	}
}