#include <bits/stdc++.h>

using namespace std;
struct muchii {
	int x,y,cost;
	bool operator < (const muchii &a) const {
		return cost<a.cost;
	}
}v[1003];
int n,m,tata[1003],suma,kontor,nod,nod1;pair <int,int> sol[1003];
int find_root (int x) {
	if(x==tata[x])
		return x;
	else {
		tata[x]=find_root(tata[x]);
		return tata[x];
	}
}
void apeme () {
	for(int i=1;i<=n;++i)
		tata[i]=i;
	for(int i=1;i<=m;++i) {
		nod=find_root(v[i].x);nod1=find_root(v[i].y);
		if(nod!=nod1)
			suma+=v[i].cost,sol[++kontor]={v[i].x,v[i].y},tata[nod]=nod1;
	}
}
int main () {
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d", &n, &m);
	for(int i=1;i<=m;++i)
		scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].cost);
	sort(v+1,v+m+1);apeme();
	printf("%d\n%d\n", suma, kontor);
	for(int i=1;i<=kontor;++i)
		printf("%d %d\n", sol[i].first, sol[i].second);
	return 0;
}