#include <iostream>
#include <algorithm>
using namespace std;
int N,M,*grupa;
struct muchie{int x,y,c;}*muchii;
struct muchienc{int x,y;}*arbore;

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

void citire()
{
freopen("apm.in","r",stdin);
cin>>N>>M;
muchii=new muchie[M+1];
arbore=new muchienc[N];
for(int i=1;i<=M;i++)
	cin>>muchii[i].x>>muchii[i].y>>muchii[i].c;
grupa=new int[N+1];
for(int i=1;i<=N;i++)
	grupa[i]=i;
sort(muchii+1,muchii+M+1,cmp);
}

int tata(int x)
{
while(x!=grupa[x])x=grupa[x];
return x;
}

int main()
{
int S=0,contor=0;
citire();
for(int i=1;i<=M;i++)
	{
	int t1=tata(muchii[i].x),t2=tata(muchii[i].y);
	if(t1!=t2)
		{
		grupa[max(t1,t2)]=min(t1,t2);
		S+=muchii[i].c;
		arbore[contor].x=muchii[i].x,arbore[contor++].y=muchii[i].y;
		}
	}

freopen("apm.out","w",stdout);
cout<<S<<'\n'<<contor<<'\n';
for(int i=0;i<contor;i++)
	cout<<arbore[i].x<<' '<<arbore[i].y<<'\n';
}