#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 bool cmp(cel a,cel b)
{   if (a.cost > b.cost)
	    return true;
	else
		return false;
}
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;
	}
	sort(v+1,v+1+n,cmp);
	n1 = n;
	for (i=1;i<=n && muchie < n1-1;++i)
	{   aux1 = v[i].x;
	    aux2 = v[i].y;
		while (aux1 != par[aux1])
			aux1 = par[aux1];
		while (aux2 != par[aux2])
			aux2 = par[aux2];
		if (aux1 != aux2)
		{   ++muchie;
		    rasp[muchie].y = v[i].x;
			rasp[muchie].x = v[i].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;
				}
		}
	}
	--n1;
	fout << cost << '\n' << n1 << '\n';
	for (i=1;i<=n1;++i)
		fout << rasp[i].x << " " << rasp[i].y << '\n';
	
	return 0;
}