#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const char InFile[]="apm.in";
const char OutFile[]="apm.out";
const int MaxN=200111;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s_edge
{
	s_edge(int x2=0,int y2=0,int cost2=0):x(x2),y(y2),cost(cost2){}
	int x,y,cost;
};

int N,M,x,y,cost,sum,T[MaxN];
vector<s_edge> e,sol;

inline bool e_cmp(s_edge a, s_edge b)
{
	return a.cost<b.cost;
}

inline void init()
{
	for(register int i=1;i<=N;++i)
	{
		T[i]=-1;
	}
}

inline int find(int x)
{
	int cx=T[x];
	int lx=x;
	while(cx>0)
	{
		lx=cx;
		cx=T[cx];
	}
	int cx2;cx=x;
	while(cx!=lx)
	{
		cx2=cx;
		cx=T[cx];
		T[cx2]=lx;
	}
	return lx;
}

inline bool unified(int x,int y)
{
	if(find(x)!=find(y))
	{
		return false;
	}
	return true;
}

inline void unify(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
	{
		if(T[fx]<T[fy])
		{
			T[fx]+=T[fy];
			T[fy]=fx;
		}
		else
		{
			T[fy]+=T[fx];
			T[fx]=fy;
		}
	}
}

int main()
{
	fin>>N>>M;
	for(register int i=0;i<M;++i)
	{
		fin>>x>>y>>cost;
		e.push_back(s_edge(x,y,cost));
	}
	fin.close();
	
	init();
	--N;
	sort(e.begin(),e.end(),e_cmp);
	for(vector<s_edge>::iterator it=e.begin();it!=e.end() && (int)(sol.size())<N;++it)
	{
		if(!unified(it->x,it->y))
		{
			unify(it->x,it->y);
			sol.push_back(*it);
			sum+=it->cost;
		}
	}
	
	fout<<sum<<"\n"<<N<<"\n";
	for(vector<s_edge>::iterator it=sol.begin();it!=sol.end();++it)
	{
		fout<<it->x<<" "<<it->y<<"\n";
	}
	fout.close();
	return 0;
}