# include <iostream>
# include <fstream>
# include <algorithm>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

# define M 400000
# define N 200000
int n,m,T[N];
struct muchie
{
	int x,y,c;
};
muchie v[M];
bool S[N];

bool comp(muchie a,muchie b)
{
	return a.c<b.c;
}

int radacina(int nod)
{
	int r;
	if(T[nod]==0)
		return nod;
	r=radacina(T[nod]);
	T[nod]=r;
	return r;
}

int main()
{
	int cost=0,nr=0,i,rx,ry;
	in>>n>>m;
	for(i=1;i<=m;i++)
		in>>v[i].x>>v[i].y>>v[i].c;
	sort(v+1,v+m+1,comp);
	for(i=1;i<=m;i++)
	{
		rx=radacina(v[i].x);
		ry=radacina(v[i].y);
		if(rx==ry)
			continue;
		nr++;
		S[i]=true;
		cost+=v[i].c;
		T[ry]=rx;
		if(nr==n-1)
			break;
	}
	out<<cost<<"\n"<<n-1<<"\n";
	for(i=1;i<=m;i++)
	{
		if(S[i])
			out<<v[i].x<<" "<<v[i].y<<"\n";
	}
	return 0;
}