using namespace std;
#include <cstdio>
#include <vector>
#include <algorithm>

struct muchie{
		int i,f,cost;
		friend bool operator <(const muchie a, const muchie b){ return a.cost<b.cost; }
	};
vector<muchie> v;
int tata[200010],n,m, ok[200010],level[200010];

int radacina(int x){
	int y=x,tmp;
	while(tata[x])
		x = tata[x];
	while(y-x)
		tmp=tata[y], tata[y] = x, y=tmp;
	return x;
}

int main(){
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	v.reserve(m+5);
	muchie mc;
	int ii,ff,cc;
	for(int i =0;i<m;i++){
		scanf("%d%d%d", &ii,&ff,&cc);
		mc.i=ii;mc.f=ff;mc.cost=cc;;
		v.push_back(mc);
	}
	sort(v.begin(), v.end());
	int ri,rf,nrm=0,cost=0;
	for(int i=0;i<m && nrm<m-1;++i)
	{
		ri=radacina(v[i].i);
		rf=radacina(v[i].f);
		if(ri!=rf)
		{
			ok[++nrm] = i;
			if(level[ri]<level[rf])
				tata[rf] = ri;
			else
				if(level[ri]>level[rf])
					tata[ri] = rf;
				else
					tata[ri] = rf, level[ri]++;
			
			cost+=v[i].cost;
			
		}
		
	}
	printf("%d\n%d\n",cost,nrm);
	for(int i=1;i<=nrm;i++)
		printf("%d %d\n",v[ok[i]].i, v[ok[i]].f);
	return 0;		
}