#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <functional>
std::ifstream fin("apm.in");
std::ofstream fout("apm.out");
bool parc[200100];
std::vector<std::pair<int, std::pair<int, int> > > v[200100], muchii, sol;
int solp = 0,parcs;
int n, m;

int main()
{
	fin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int a, b, cost;
		fin >> a >> b >> cost;
		v[a].push_back(std::make_pair(cost, std::make_pair(b, a)));
		v[b].push_back(std::make_pair(cost, std::make_pair(a, b)));
	}
	int front = 1;
	std::make_heap(muchii.begin(),muchii.end());
	while (parcs!=n) {
		parc[front] = 1;
		parcs++;
		for (std::vector<std::pair<int, std::pair<int, int> > >::iterator i = v[front].begin(); i != v[front].end(); ++i)
		{
			if(!parc[i->second.first]||!parc[i->second.second]){
				muchii.push_back(*i);
				std::push_heap(muchii.begin(),muchii.end(),std::greater<std::pair<int, std::pair<int, int> > >());
			}
		}
		while(!muchii.empty()){
			std::pair<int, std::pair<int, int> > i=muchii.front();
			std::pop_heap(muchii.begin(),muchii.end(),std::greater<std::pair<int, std::pair<int, int> > >());
			muchii.pop_back();
			if (!parc[i.second.first]) {
				front = i.second.first;
				sol.push_back(i);
				solp+=i.first;
				break;
			}
			if((i.second.first==front)&&!parc[i.second.second]){
				front = i.second.second;
				sol.push_back(i);
				solp+=i.first;
				break;
			}
		}
	}
	fout<<solp<<"\n";
	fout<<sol.size()<<"\n";
	for (std::vector<std::pair<int, std::pair<int, int> > >::iterator i = sol.begin(); i != sol.end(); ++i)
	{
		fout << i->second.first << " " << i->second.second <<"\n";
	}
	fout.flush();
	std::cout<<"Done";
}