#include <bits/stdc++.h>
using namespace std;

int p[200001], n, m, sum;
priority_queue<pair<int, pair<int, int> > > q;
queue<pair<int, int> > v;

int find(int x)
{
	if (p[x] == x)
		return x;
	else
		return p[x] = find(p[x]);
}

void unite(int x, int y, int z)
{
	int a = find(x);
	int b = find(y);
	p[b] = a;
	sum += z;
	v.push({x, y});
}

int main()
{
	ifstream cin("apm.in");
	ofstream cout("apm.out");
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		p[i] = i;
	for (int l = 1; l <= m; l++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		q.push({-z, {x, y}});
	}
 	int k = 1;
 	while (k < n)
 	{
 		pair<int, pair<int, int> > temp = q.top();
 		q.pop();
 		temp.first = -temp.first;
 		if (find(temp.second.first) != find(temp.second.second))
 			unite(temp.second.first, temp.second.second, temp.first), k++;
	}
	cout << sum << '\n' << n - 1 << '\n';
	while (!v.empty())
	{
		pair<int, int> temp = v.front();
		v.pop();
		cout << temp.first << ' ' << temp.second << '\n';
	}
	return 0;
}