#include<fstream>
using namespace std;
ofstream fout("apm.out");
struct muchie
{
	int x,y,c;
};
muchie v[400001];
int n,m,s,index[400001],nr;
void citire();
void sort(int ,int );
void kruskal();
void afisare();
int main()
{
	citire();
	sort(1,m);
	kruskal();
	afisare();
}
void citire()
{
	ifstream fin("apm.in");
	fin>>n>>m;;
	int i,j,k;
	for(int z=1;z<=m;z++)
	{
		fin>>i>>j>>k;
		v[z].x=i;
		v[z].y=j;
		v[z].c=k;
	}
}
void sort(int st,int dr)
{
	if(st<dr)
	{
		int i=st,j=dr,d=0;
		while(i<j)
		{
			if(v[i].c>v[j].c)
			{
				muchie  aux=v[i];
				v[i]=v[j];
				v[j]=aux;
				d=1-d;
			}
			if(d==0)
				j--;
			else
				i++;
		}
		sort(st,i-1);
		sort(i+1,dr);
	}
}
void kruskal()
{
	int p[200001];
	for(int i=1;i<=n;i++)
		p[i]=i;
	for(int i=1;i<=m;i++)
		if(p[v[i].x]!=p[v[i].y])
		{
			s+=v[i].c;
			index[++nr]=i;
			int a,b;
			a=max(p[v[i].x],p[v[i].y]);
			b=min(p[v[i].x],p[v[i].y]);
			for(int j=1;j<=n;j++)
				if(p[j]==a)
					p[j]=b;
			
	}
}
void afisare()
{
	fout<<s;
	fout<<'\n';
	fout<<nr;
	fout<<'\n';
	for(int i=1;i<n;i++)
		fout<<v[index[i]].x<<" "<<v[index[i]].y<<"\n";

}