#include <fstream>
#include <queue>
#include <utility>
#include <vector>
#include <sstream>
#include <algorithm>
//#define sn second
//#define fs first
//#define mkp make_pair
#define push_pair(A,B) push_back(make_pair(A,B))
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

deque<pair<pair<int,int>, int> > g;
vector<pair<int,int> > res;
int n,m,i,j,k,a1,a2,a3,gr[200010],c,to_find;
bool there;

bool cmp(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b)
{
	return a.second < b.second;
}

int main()
{
	in>>n>>m;
	for(i=1; i<=m; i++)
	{
		in>>a1>>a2>>a3;
		g.push_pair(make_pair(a1,a2),a3);
	}
	sort(g.begin(), g.end(), cmp);
	
	for(i=1; i<=n; i++)
		gr[i]=i;
	for(k=n;k>1;k--)
	{
		while(gr[g.front().first.first] == gr[g.front().first.second])
			g.pop_front();
		res.push_pair(g.front().first.first, g.front().first.second);
		c+=g.front().second;
		to_find = gr[g.front().first.second];
		for(i=1; i<=n; i++)
			if(gr[i] == to_find)
				gr[i]=gr[g.front().first.first];
		g.pop_front();
	}
	out<<c<<'\n'<<res.size()<<'\n';
	for(vector<pair<int,int> >::iterator it=res.begin(); it!=res.end(); it++)
		out<< it->second<<' '<< it->first<<'\n';
	
	return 0;
}