#include <fstream>
#include<algorithm>
using namespace std;
struct ura
{
	int   a, b, c;
}v[200002];
int rez[200002];
bool cmp(ura a, ura b)
{
	if (a.c<b.c)
		return true;
	return false;
}
int sef[200002];
int find(int i) {
  if (sef[i]==i)
    return i;
  return sef[i]=find(sef[i]);
}
void unite( int i, int j ) {
  int sef1, sef2;
  sef1=find(i);
  sef2=find(j);
  sef[sef1]=sef2;
}
ifstream cin("apm.in");
ofstream cout("apm.out");
int main()
{
    int n,m, i, x, y, cost;
    cin>>n>>m;
    for (i=1;i<=n;i++)
	{
		sef[i]=i;
	}
    for (i=1;i<=m;i++)
	{
		cin>>x>>y>>cost;
		v[i].c=cost;
		v[i].a=x;
		v[i].b=y;
	}
	sort(v+1, v+1+m, cmp);
	cost=0;
	int poz=0;
	for (i=1;i<=m;i++)
	{
		if (find(v[i].a)!=find(v[i].b))
		{
			rez[++poz]=i;
			unite(v[i].a, v[i].b);
			cost+=v[i].c;
		}
		if (poz==n)
		{
			i=m+1;
		}
	}
	cout<<cost<<'\n'<<poz<<'\n';
	for (i=1;i<=poz;i++)
	{
		cout<<v[rez[i]].a<<" "<<v[rez[i]].b<<'\n';
	}
    return 0;
}