#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define lung 200001
struct cel{int x,y,cost;
};
int n,m,i,nr,rasp[lung],grad[lung],par[lung],aux1,aux2,cost;
cel v[400001];
inline int parinte(int k)
{   while (k != par[k])
		k = par[k];
    return k;
}
inline bool cmp(cel a,cel b)
{   if (a.cost < b.cost)
		return 1;
    return 0;
}
int main()
{   fin >> n >> m;
    for (i=1;i<=n;++i)
		par[i] = i;
    for (i=1;i<=m;++i)
	 	fin >> v[i].x >> v[i].y >> v[i].cost;
	sort(v+1,v+1+m,cmp);
	for (i=1;i<=m && nr < n;++i)
	{   aux1 = parinte(v[i].x);
	    aux2 = parinte(v[i].y);
		if (aux1 != aux2)
		{   rasp[++nr] = i;
		    cost+= v[i].cost;
			if (grad[aux1] < grad[aux2])
			    par[aux1] = aux2;
			else
			{   par[aux2] = aux1;
			    if (grad[aux1] == grad[aux2])
					++grad[aux1];
			}
		}
	}
	fout << cost << '\n' << nr << '\n';
	for (;nr;--nr)
		fout << v[rasp[nr]].x << " " << v[rasp[nr]].y << '\n';
	return 0;
}