#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 Edge
{
	Edge(int x=0, int y=0, int cost=0):x(x),y(y),cost(cost){}
	int x,y,cost;
};

struct Edge_CMP
{
	inline bool operator() (const Edge &a, const Edge &b)
	{
		return a.cost<b.cost;
	}
};

int N,M,PMD[MaxN],apmcost,x,y,cost;
vector<Edge> G,apm;

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

inline int Root(int x)
{
	int t=x;
	while(PMD[t]>0)
	{
		t=PMD[t];
	}
	
	while(x!=t)
	{
		int aux=PMD[x];
		PMD[x]=t;
		x=aux;
	}
	return t;
}

inline bool Unified(const int &x, const int &y)
{
	return Root(x)==Root(y);
}

inline void Unify(const int &x, const int &y)
{
	int ry=Root(y);
	int rx=Root(x);
	if(ry!=rx)
	{
		if(PMD[rx]<PMD[ry])
		{
			PMD[rx]+=PMD[ry];
			PMD[ry]=rx;
		}
		else
		{
			PMD[ry]+=PMD[rx];
			PMD[rx]=ry;
		}
	}
}

inline void Kruskal()
{
	apmcost=0;
	
	Init_PMD();
	
	sort(G.begin(),G.end(),Edge_CMP());
	for(vector<Edge>::iterator it=G.begin();it!=G.end();++it)
	{
		if(!Unified(it->x,it->y))
		{
			Unify(it->x,it->y);
			apmcost+=it->cost;
			apm.push_back(*it);
		}
	}
}

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=M;++i)
	{
		fin>>x>>y>>cost;
		G.push_back(Edge(x,y,cost));
	}
	fin.close();
	
	Kruskal();
	
	fout<<apmcost<<"\n";
	fout<<apm.size()<<"\n";
	for(vector<Edge>::iterator it=apm.begin();it!=apm.end();++it)
	{
		fout<<it->x<<" "<<it->y<<"\n";
	}
	fout.close();
	return 0;
}