#include<fstream>
#include<algorithm>
using namespace std;
struct muchie
{
	int i,j;
	int cost;
	friend bool operator < (const muchie &a, const muchie &b)
	{ return a.cost<b.cost; }
};
muchie v[400005];
int n,m,t[200002],a[200002],h[200002],na;

int radacina(int x)
{
	int y=x,tmp;
	while(t[x]!=0)
		x=t[x];
	while(t[y])
		tmp=t[y],t[y]=x,y=tmp;
	return x;
}
int main()
{
	ifstream fin("apm.in");
	fin>>n>>m;
	for(int i=1;i<=m;++i)
		fin>>v[i].i>>v[i].j>>v[i].cost;
	fin.close();
	sort(v+1,v+m+1);
	for(int i=1;i<=m;++i)
	{
		int ri=radacina(v[i].i), rj=radacina(v[i].j);
		if(ri!=rj)
		{
			a[na++]=i;
			if(h[ri]<h[rj])
			  t[ri]=rj;
			else
				if(h[ri]>h[rj])
					t[rj]=ri;
				else
					t[ri]=rj,h[rj]++;
		}
	}
	int s=0;
	for(int i=0;i<na;++i)
		s+=v[a[i]].cost;
	ofstream fout("apm.out");
	fout<<s<<'\n'<<na<<'\n';
	for(int i=0;i<na;++i)
	   fout<<v[a[i]].i<<' '<<v[a[i]].j<<'\n';
    fout.close();
	return 0;
}