# include <cstdio>
# include <algorithm>

using namespace std;

class muchie 
{
public:
	int x,y,c;
	bool operator< (const muchie& other) const 
	{ 
		return c<other.c; 
	} 

} M[40005],sol[20005];

int tt[20005],h[20005];
int cost,poz,n,m,rad1,rad2,i,j;

int find (int x)
{
	int rad=x,aux;
	while (tt[rad]!=0)
		rad=tt[rad];
	while (tt[x]!=rad&&tt[x]!=0)
	{
		aux=tt[x];
		tt[x]=rad;
		x=aux;
	}
	return rad;
}

void UNION (int rad1, int rad2)
{
	if (h[rad1]<h[rad2])
		tt[rad1]=rad2;
	else
	{
		tt[rad2]=rad1;
		if (h[rad1]==h[rad2])
			h[rad1]++;
	}
}

int main ()
{
	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",&M[i].x,&M[i].y,&M[i].c);
	sort(M+1,M+m+1);
	poz=1;
	for (i=1;i<n;i++)
	{
		rad1=find(M[poz].x); 
    rad2=find(M[poz].y);
		while (rad1==rad2)
		{
			poz++;
			rad1=find(M[poz].x); rad2=find(M[poz].y);
		}
		sol[i]=M[poz]; cost+=M[poz].c;
		UNION(rad1,rad2);
	}
	printf("%d\n%d\n",cost,n-1);
	for (i=1;i<=n-1;i++)
		printf("%d %d\n",sol[i].x,sol[i].y);
	return 0;
}