#include<cstdio>
#include<algorithm>
using namespace std;
const int MMAX=400005;
const int NMAX=200005;
struct MUCHIE{
	int u,v,c;
}v[MMAX];
int t[NMAX],h[NMAX],vec[NMAX];
bool cmp(MUCHIE a, MUCHIE b){
	return a.c<=b.c;
}
int FindSet(int x){
	while(x!=t[x])
		x=t[x];
	return x;
}
bool UnionSet(int x, int y){
	int tx,ty;
	tx=FindSet(x);
	ty=FindSet(y);
	if(tx==ty)
		return 0;
	if(h[tx]==h[ty]){
		h[tx]++;
		t[ty]=tx;
	}
	else
		if(h[tx]<h[ty])
			t[tx]=ty;
		else
			t[ty]=tx;
		return 1;
}
int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m;
		scanf("%d%d", &n, &m);
		for(int i=1;i<=m;i++)
			scanf("%d%d%d", &v[i].u, &v[i].v, &v[i].c);
		sort(v+1, v+m+1, cmp);
		for(int i=1;i<=n;i++)
			t[i]=i;
		for(int i=1;i<=n;i++)
			h[i]=1;
		int nrop=0,cost=0;
		for(int i=1;nrop<=n-1 && i<=m;i++){
			bool ok=UnionSet(v[i].u, v[i].v);
			if(ok==1){
				nrop++;
				vec[nrop]=i;
				cost+=v[i].c;
			}
		}
		printf("%d\n%d\n", cost, n-1);
		for(int i=1;i<=nrop;i++)
			printf("%d %d\n", v[vec[i]].u, v[vec[i]].v);
    return 0;
}