//kruskal bc

#include <stdio.h>
#define max 400001

struct muchie {int x,y,cost,da;} z[max];

int n,m,cost,nrsol;
int poz[max],r[max];

int mult(int x)
{
	if(poz[x]==x)
		return poz[x];
	poz[x]=mult(poz[x]);
	return poz[x];
}

void reun(int x, int y)
{
	x=mult(x);
	y=mult(y);
	if(r[x]>r[y])
		poz[y]=x;
	else
	{
		poz[x]=y;
		if(r[x]==r[y])
			r[y]++;
	}
}

void kruskal()
{
	int m1,m2;
	for(int i=1;i<=m;i++)
	{
		m1=mult(z[i].x);
		m2=mult(z[i].y);
		if(m1!=m2)
		{
			nrsol++;
			cost+=z[i].cost;
			z[i].da=1;
			reun(m1,m2);
		}
	}
}

void swap(muchie &x, muchie &y)
{
	muchie aux;
	aux=x;
	x=y;
    y=aux;
}

void sort(muchie arr[], int beg, int end)
{
	if(end>beg+1)
	{
		muchie piv=arr[beg];
		int l=beg+1,r=end;
		while(l<r)
		{
			if(arr[l].cost<piv.cost)
			  l++;
			else
			  swap(arr[l], arr[--r]);
		}
		swap(arr[--l], arr[beg]);
		sort(arr, beg, l);
		sort(arr, r, end);
	}
}

int main()
{
	int i;
	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",&z[i].x,&z[i].y,&z[i].cost);
		if(i<=n)
			poz[i]=i;
	}
	sort(z,1,m+1);
	kruskal();
	printf("%d\n%d\n",cost,nrsol);
	for(i=1;i<=m;i++)
		if(z[i].da==1)
        	printf("%d %d\n",z[i].x,z[i].y);
	fclose(stdout);
	return 0;
}