#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
typedef struct{int x,y,cost;}cel;
typedef struct{int x,y;}cel1;
int i,n,m,n1,cost,muchie,aux1,aux2,par[2000001],grad[200001];
cel v[400001],aux;
cel1 rasp[200001];
inline int cmp(cel a,cel b)
{   if (a.cost > b.cost)
	    return 1;
	else
		return 0;
}
inline int scufund(int k)
{int tot=k;
    if (k*2 <= m && v[2*k].cost < v[k].cost)
		tot = 2*k;
	if (k*2+1 <= m && v[2*k+1].cost < v[tot].cost)
		tot = k*2+ 1;
	if (k != tot)
	{   aux = v[k];
	    v[k] = v[tot];
		v[tot] = aux;
		scufund(tot);
	}
	return 0;
}
int main()
{   fin >> n >> m;
    for (i=1;i<=m;++i)
	{   fin >> v[i].x >> v[i].y >> v[i].cost;
	    par[i] = i;
		grad[i] = 1;
	}
	make_heap(v+1,v+1+m,cmp);
	n1 = n;
	while (muchie < n1-1)
	{   aux1 = v[1].x;
	    aux2 = v[1].y;
		while (aux1 != par[aux1])
			aux1 = par[aux1];
		while (aux2 != par[aux2])
			aux2 = par[aux2];
		if (aux1 != aux2)
		{   ++muchie;
		    rasp[muchie].y = v[1].x;
			rasp[muchie].x = v[1].y;
		    cost = cost + v[1].cost;
			if (grad[aux1] < grad[aux2])
				par[aux1] = aux2;
			else
				if (grad[aux1] > grad[aux2])
					par[aux2] = aux1;
				else
				{   ++grad[aux1];
				    par[aux2] = aux1;
				}
		}
		aux = v[1];
		v[1] = v[m];
		v[m] = v[1];
		--m;
		scufund(1);
	}
	--n1;
	fout << cost << '\n' << n1 << '\n';
	for (i=1;i<=n1;++i)
		fout << rasp[i].x << " " << rasp[i].y << '\n';
	
	return 0;
}