#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;

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

string show(deque<pair<pair<int,int>, int> > g)
{
	stringstream s;
	s<<"[ ";
	for(deque<pair<pair<int,int>, int> >::iterator it=g.begin(); it!=g.end();it++)
		s<<"("<< it->fs.fs <<","<< it->fs.sn<<" -> "<< it->sn<<")";
	return s.str();
}

int main()
{
	in>>n>>m;
	for(i=1; i<=m; i++)
	{
		in>>a1>>a2>>a3;
		g.push_pair(mkp(a1,a2),a3);
		//g.push_pair(mkp(a2,a1),a3);
	}
	sort(g.begin(), g.end(), cmp() );
	
	for(i=1; i<=n; i++)
		gr[i]=i;
	for(k=n;k--;k>1)
	{
		while(!g.empty() && gr[g.front().fs.fs] == gr[g.front().fs.sn])
			g.pop_front();
		if(g.empty())
			break;
		res.push_pair(g.front().fs.fs, g.front().fs.sn);
		c+=g.front().sn;
		there = true;
		to_find = gr[g.front().fs.sn];
		for(i=0; i<=n+1; i++)
			if(gr[i] == to_find)
				gr[i]=gr[g.front().fs.fs];
			else if(gr[i] != gr[g.front().fs.fs])
				there = false;
		if(there || g.empty())
			break;
		g.pop_front();
	}
	out<<c<<'\n'<<res.size()<<'\n';
	for(vector<pair<int,int> >::iterator it=res.begin(); it!=res.end(); it++)
	{
		out<< it->sn<<' '<< it->fs<<'\n';
	}
	
	return 0;
}