#include<fstream>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchii
{
	int x,y,c;
};
muchii L[400001];
int t[200001],n,m,cost,s[2][400001],nr;
void citire()
{	 int i;
	f>>n>>m;
	for(i=1;i<=m;i++)
		f>>L[i].x>>L[i].y>>L[i].c;
	for(i=1;i<=n;i++)
		t[i]=i;
}
int cmp(muchii a,muchii b)
{
	return a.c<b.c;
}
void afisare()
{
	g<<cost<<'\n'<<n-1<<'\n';
	for(int i=1;i<=n-1;i++)
		g<<s[0][i]<<" "<<s[1][i]<<'\n';
}
int radacina(int nod)
{
	if(t[nod]!=nod)
		t[nod]=radacina(t[nod]);
	return t[nod];
}
void kruskal()
{
	int i,yi,xi;
	nr=0;
	for(i=1;i<=m&&nr<n-1;i++)
	{
		xi=radacina(L[i].x);
		yi=radacina(L[i].y);
		if(xi!=yi)
		{
			nr++;
			s[0][nr]=L[i].x;
			s[1][nr]=L[i].y;
			t[yi]=xi;cost+=L[i].c;
		}
	}
	afisare();
}
int main()
{
	
	citire();
	sort(L+1,L+m+1,cmp);
	kruskal();
	return 0;
}