#include<fstream>
#include<vector>
#include<set>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector< pair<int, int> > vec[200001];
set<pair <int,int> > heap;
int apm[200001],mc[200001];
int main()
{
	int n, m, x, y, v, i, s = 0, ok=1,cnt=1;
	f >> n >> m;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y >> v;
		vec[x].push_back(make_pair(y, v));
		vec[y].push_back(make_pair(x, v));
	}
	/*for (i = 1; i <= n; i++)
		mc[i] = 1001;*/
	/*vector< pair<int, int> >::iterator it;
	for (it = vec[1].begin(); it != vec[i].end(); it++)
		mc[it->first] = it->second; */
	vector< pair<int, int> >::iterator it;
	for (it = vec[1].begin(); it != vec[1].end(); it++)
	{
		heap.insert(make_pair(it->second, it->first));
	}
	apm[1] = 1;
	while (cnt < n)
	{
		cnt++;
		set< pair<int, int> >::iterator it2;
		it2 = heap.begin();
		while (apm[it2->second])
		{
			heap.erase(heap.begin());
			it2 = heap.begin();
		}
		apm[it2->second] = 1;
		mc[it2->second] = it2->first;
		s += it2->first;
		vector< pair<int, int> >::iterator it;
		for (it = vec[it2->second].begin(); it != vec[it2->second].end(); it++)
		{
			heap.insert(make_pair(it->second, it->first));
		}
	}
	g << s << '\n' << n - 1<<'\n';
	for (i = 1; i <= n; i++)
	{
		ok = 1;
		vector< pair<int, int> >::iterator it;
		for (it = vec[i].begin(); it != vec[i].end() && ok; it++)
		{
			if (mc[i] == it->second)
			{
				g << i << " " << it->first << '\n';
				ok = 0;
			}
		}
	}
}