#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#define C first
#define X second.first
#define Y second.second
using namespace std;
void read(),solve();
vector<int> vx,vy;
pair< int, pair< int , int > > M[400100];
int n,m,i,j,x,y,rx,ry,c,a,b,cost,used,U[200100],T[200100];
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		M[i]=make_pair( c , make_pair(a,b) ) ;
	}
}
void solve()
{
	sort(M+1,M+m+1);
	vector<int>::iterator it;
	for(i=1;i<=n;i++)
		T[i]=i;
	for(j=1;j<=m;j++)
	{
		if(used==n-1)break;
		x=M[j].X; 
		y=M[j].Y;
		vx.resize(0); vy.resize(0);
		for(i=x;;){vx.push_back(i);if(T[i]==i){rx=i;break;}i=T[i];}
		for(i=y;;){vy.push_back(i);if(T[i]==i){ry=i;break;}i=T[i];}
		if(rx!=ry){cost+=M[j].C;U[++used]=j;rx=ry;}		
		for(it=vx.begin();it!=vx.end();it++)T[*it]=rx;
		for(it=vy.begin();it!=vy.end();it++)T[*it]=ry;
	}
	printf("%d\n",cost);
	printf("%d\n",used);
	for(i=1;i<=used;i++)
		printf("%d %d\n",M[U[i]].X,M[U[i]].Y);
}