#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[i].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);
}