#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct fint
{
	int x,y,c;
};
struct xyz
{
	int x,y;
};
fint v[400005];
xyz sol[200005];
int t[200005],h[200005];
int nr,s;
bool cmp(fint a,fint b)
{
	return a.c<b.c;
}
int findset(int x)
{
	while(t[x]!=x)
		x=t[x];
	return x;
}
void unite(int x,int y,int a,int b,int o)
{
	if(h[x]==h[y])
	{
		t[y]=x;
		h[x]++;
		nr++;
		sol[nr].x=a;
		sol[nr].y=b;
		s+=v[o].c;
	}
	else	
		{
		if(h[x]>h[y])
			t[y]=x;
		else 
			t[x]=y;
		nr++;
		sol[nr].x=a;
		sol[nr].y=b;
		s+=v[o].c;
		}
}
int main()
{
	int n,m,i,j;
	cin>>n>>m;
	for(i=1;i<=m;i++)
		cin>>v[i].x>>v[i].y>>v[i].c;
	sort(v+1,v+m+1,cmp);
	for(i=1;i<=n;i++)
		{
		t[i]=i;
		h[i]=1;
		}
	for(i=1;i<=m;i++)
	{
		int x=findset(v[i].x),y=findset(v[i].y);
		if(x!=y)
			unite(x,y,v[i].x,v[i].y,i);
		if(nr==n-1)
			break;
	}
	cout<<s<<"\n"<<n-1<<"\n";
	for(i=1;i<=nr;i++)
	{
		cout<<sol[i].y<<" "<<sol[i].x<<"\n";
	}
    cin.close();
    cout.close();
	return 0;
}