#include<fstream>
#include<vector>
#include<queue>
#include<utility>
#define pi pair<int, int>
using namespace std;
struct edge
{
	int nod1, nod2, cost;
};
struct cmp
{
	bool operator() ( const edge &edge1, const edge &edge2) const
	{
		return edge1.cost>edge2.cost;
	}
};

int apm_cost;
queue<pi>sol;
vector< vector<pi> >m(400001);
bool ch[200001];
ofstream g("apm.out");

void prim(int root, int n);
int main()
{
	ifstream f("apm.in");
	int n, nrm, i, x, y, c;
	f>>n>>nrm;
	for(i=1;i<=nrm;i++) 
	{
		f>>x>>y>>c;
		m[x].push_back(make_pair(y, c));
		m[y].push_back(make_pair(x, c));
	}
	/*for(i=1;i<=n;i++)
	{
		if(!m[i].empty())
		{
			g<<i;
			for(vector<pi>::iterator it=m[i].begin();it!=m[i].end();++it, g<<"\n")
				g<<":  ("<<(*it).first<<" "<<(*it).second<<") ";
		}
	}*/
	prim(1, n);
	g<<apm_cost<<"\n";
	g<<sol.size()<<"\n";
	while(!sol.empty())
		g<<sol.front().first<<" "<<sol.front().second<<"\n", sol.pop();
	f.close();
	g.close();
	return 0;
}
void prim(int root, int n)
{
	ch[root]=true;
	edge e, e2;
	priority_queue<edge, vector<edge>, cmp> Q;
	for(vector<pi>::iterator it=m[root].begin(); it!=m[root].end();++it)
		if(!ch[(*it).first])
		{
			e.nod1=root;
			e.nod2=(*it).first;
			e.cost=(*it).second;
			Q.push(e);
		}
	for(int i=1;i<n;i++)
	{
		e=Q.top();
		Q.pop();
		while(ch[e.nod1] && ch[e.nod2])
		{
			e=Q.top();
			Q.pop();
		}
		apm_cost+=e.cost;
		ch[e.nod2]=ch[e.nod1]=true;
		e2.nod1=e.nod2;
		for(vector<pi>::iterator it=m[e.nod2].begin(); it!=m[e.nod2].end(); ++it)
			if(!ch[(*it).first])
			{
				e2.nod2=(*it).first;
				e2.cost=(*it).second;
				Q.push(e2);
			}
		sol.push(make_pair(e.nod1, e.nod2) );
	}
}