#include <fstream>
using namespace std;

const int N=200001,M=400001;
struct arc{int x,y,c;} a[M];
int v[N],sol[M],size[N],n,m,cost;

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

inline bool cmp(arc a,arc b)
{
	return a.c<b.c;
}

inline int varf(int x)
{
	if (v[x]==x)
		return x;
	v[x]=varf(v[x]);
	return v[x];
}

inline void merge(int x,int y)
{
	if (size[x]>size[y])
	{
		size[x]+=size[y];
		v[y]=x;
		return;
	}
	size[y]+=size[x];
	v[x]=y;
}

int main()
{
	in>>n>>m;
	int x,y,i;
	for (i=1;i<=n;i++)
	{
		v[i]=i;
		size[i]=1;
	}
	for (i=1;i<=m;i++)
		in>>a[i].x>>a[i].y>>a[i].c;
	sort(a+1,a+m+1,cmp);
	for (i=1;i<=m;i++)
	{
		x=varf(a[i].x);
		y=varf(a[i].y);
		if (x!=y)
		{
			cost+=a[i].c;
			sol[++sol[0]]=i;
			merge(x,y);
		}
	}
	out<<cost<<"\n"<<sol[0]<<"\n";
	for (i=1;i<=sol[0];i++)
		out<<a[sol[i]].x<<" "<<a[sol[i]].y<<"\n";
	return 0;
}