#include <fstream>
#include <algorithm>
#define NM 200001
#define MM 400000
using namespace std;
struct muchie
{
	int x,y,c;
}m[MM];
int N,M,a[NM],v[NM],vc,s;
int Root(int i)
{
	while(a[i])
		i=a[i];
	return i;
}
void Unite(int i,int j)
{
	a[Root(i)]=Root(j);
}
bool cmp(muchie a,muchie b)
{
	return a.c<=b.c;
}
ifstream fin("apm.in");
ofstream fout("apm.out");
int main()
{
	int i;
	fin>>N>>M;
	for(i=0;i<M;i++)
		fin>>m[i].x>>m[i].y>>m[i].c;
	sort(m,m+M,cmp);
	for(i=0;i<M;i++)
		if(Root(m[i].x)!=Root(m[i].y))
		{
			s+=m[i].c;
			Unite(m[i].x,m[i].y);
			v[vc++]=i;
		}
	N--;
	fout<<s<<"\n"<<N<<"\n";
	for(i=0;i<N;i++)
		fout<<m[v[i]].x<<" "<<m[v[i]].y<<"\n";
	return 0;
}