# include <cstdio>
# include <iostream>
using namespace std;
struct nod{
	int i, j, c;};
int n, nm, t[200003], cmin, v[400003], rang[200003];
nod m[400003];

void cerne (int k, int n)
{
	int i, eh=0;
	while (!eh && 2*k<=n)
	{
		i=2*k;
		if (i+1<=n && m[i+1].c<m[i].c)
			i++;
		if (m[k].c<=m[i].c)
			eh=1;
		else
		{
			nod a;
			a=m[k], m[k]=m[i], m[i]=a;
			k=i;
		}
	}
}

void promoveaza (int k)
{
	int eh=0;
	while (k/2 && !eh)
	{
		if (m[k/2].c<=m[k].c)
			eh=1;
		else
		{
			nod a;
			a=m[k], m[k]=m[k/2], m[k/2]=a;
			k=k/2;
		}
	}
}

void hsort (int n)
{
	for (;n;)
	{
		nod a;
		a=m[1], m[1]=m[n], m[n]=a;
		n--;
		cerne (1, n);
	}
}

int rad (int k)
{
	int y=k, i;
	while (t[k]) k=t[k];
	while (y!=k)
	{
		i=t[y];
		t[y]=k;
		y=i;
	}
	return k;
}

int main ()
{
	int ri, rj, nrm=0;
	freopen ("apm.in", "r", stdin);
	freopen ("apm.out", "w", stdout);
	scanf("%d%d", &n, &nm);
	for (int i=1;i<=nm;i++)
	{
		scanf("%d%d%d", &m[i].i, &m[i].j, &m[i].c);
		promoveaza (i);
	}
	hsort (nm);
	for (int i=nm;i && nrm<=n-1;i--)
		if ((ri=rad(m[i].i))!=(rj=rad(m[i].j)))
		{
			if (rang[ri]<rang[rj])
				t[ri]=rj;
			else
				if(rang[ri]>rang[rj])
					t[rj]=ri;
				else
				{				
					t[ri]=rj;
					rang[rj]++;
				}				
				cmin+=m[i].c;
				v[i]=1;
				nrm++;
		}
	printf("%d\n%d\n", cmin, n-1);
	for (int i=1;i<=nm;i++)
		if (v[i])
			printf("%d %d\n", m[i].i, m[i].j);
	return 0;
}