#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,i,t[200010],rx,ry,k,sol[400010],sum;
struct muchie{
	int x,y,cost;
};
muchie v[400010];
bool cmp(const muchie &a, const muchie &b) {
	return (a.cost<b.cost);
}
int rad(int nod) {
	while (t[nod]>0)
		nod=t[nod];
	return nod;
}
int main() {
	fin>>n>>m;
	for (i=1;i<=n;i++)
		t[i]=-1;
	for (i=1;i<=m;i++)
		fin>>v[i].x>>v[i].y>>v[i].cost;
	sort(v+1,v+m+1,cmp);
	for (i=1;i<=m;i++) {
		rx=rad(v[i].x); ry=rad(v[i].y);
		//un fel de greedy
		if (rx!=ry) {
			sol[++k]=i;
			sum+=v[i].cost;
			if (t[rx]<t[ry]) {
				t[rx]+=t[ry];
				t[ry]=rx;
			}
			else {
				t[ry]+=t[rx];
				t[rx]=ry;
			}
		}
	}
	fout<<sum<<"\n"<<n-1<<"\n";
	for (i=1;i<=k;i++)
		fout<<v[sol[i]].x<<" "<<v[sol[i]].y<<"\n";
	return 0;
}