#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int lim = 2e5 + 5;
int n, m;
struct edge {
	int x, y, cost;
};
int ans;
vector<edge> sol;
vector<edge> g;
int TT[lim];
int sz[lim];
int find(int x)
{
	if (!TT[x])
		return x;
	return TT[x] = find(TT[x]);
}
void unite(int x, int y)
{
	int tx = find(x), ty = find(y);
	if (tx != ty)
	{
		if (sz[tx] < sz[ty])
			TT[tx] = ty;
		else
		{
			TT[ty] = tx;
			if (sz[tx] == sz[ty])
				sz[tx] ++;
		}
	}
}


int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		edge a;
		cin >> a.x >> a.y >> a.cost;
		g.push_back(a);
	}
	sort(g.begin(), g.end(), [](const edge& a, const edge& b) {return a.cost < b.cost; });
	for (const auto& it : g)
		if (find(it.x) != find(it.y)) 
		{
			unite(it.x, it.y);
			ans += it.cost;
			sol.push_back(it);
		}
	cout << ans << '\n' << sol.size() << '\n';
	for (const auto& it : sol)
		cout << it.x << " " << it.y << '\n';
}