#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define dim 20005
int n , m, nrm, cost, t[dim], r[dim];
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{int x, y, c;}v[dim*2];
muchie sol[dim];

int cmp(muchie a, muchie b)
{
	return a.c<b.c;
}

void read()
{
	fin>>n >>m;
	for(int i=1;i<=m;++i)
		fin>>v[i].x >>v[i].y >>v[i].c;
}

int find(int x)
{
	if(x!=t[x])
		t[x]=find(t[x]);
	return t[x];
}

inline void unite(int x, int y)
{
	if(r[x]<r[y])
		t[x]=y;
	else
		t[y]=x;
	if(r[x]==r[y])
		++r[x];
}

void solve()
{
	int i;
	
	for(i=1;nrm<n-1 && i<=m;++i)
		if( find(v[i].x)!=find(v[i].y) )
		{
			cost+=v[i].c;
			sol[++nrm]=v[i];
			unite( find(v[i].x), find(v[i].y) );
		}
}
	
void tipar()
{
	fout<<cost<<'\n';
	fout<<nrm <<'\n';
	for(int i=1;i<=nrm;++i)
		fout<<sol[i].x <<" "<<sol[i].y <<'\n';
}

int main()
{
	read();
	for(int i=1;i<=n;++i)
		t[i]=i;
	sort(v+1,v+m+1,cmp);
	solve();
	tipar();
	return 0;
}