#include<cstdio>
#include<algorithm>
using namespace std;
struct MUCHIE {
	long x,y,c;
};
MUCHIE w[400001];
long sol[200001];
long t[200001];
long h[200001];
long n,m,i;
void read () {
	long i;
	scanf("%ld%ld",&n,&m);
	for (i=1;i<=m;i++)
		scanf("%ld%ld%ld",&w[i].x,&w[i].y,&w[i].c);
}

long find (long x) {
	long y,r;
	for (r=x;t[r]!=r;r=t[r]);
	while (t[x]!=x) {
		y=t[x];
		t[x]=r;
		x=y;
	}
	return r;
}

void Union (long x, long y) {
	if (h[x]>h[y])
		t[y]=x;
	else
		if (h[y]>h[x])
			t[x]=y;
		else
			if (h[y]==h[x]) {
				h[x]++;
				t[y]=x;
			}
}

inline bool cmp (MUCHIE A , MUCHIE B) {
	if (A.c<=B.c)
		return 1;
	return 0;
}

void solve () {
	long i,s=0,num=0,rx,ry,u=0;
	sort(w+1,w+1+m,cmp);
	for (i=1;i<=n;i++)
		t[i]=i;
	for (i=1;num<n-1;i++) {
		rx=find(w[i].x);
		ry=find(w[i].y);
		if (rx!=ry) {
			s=s+w[i].c;
			num++;
			Union(rx,ry);
			sol[++u]=i;
		}
	}
	printf("%ld\n%ld\n",s,n-1);
	for (i=1;i<=u;i++)
		printf("%ld %ld\n",w[sol[i]].y,w[sol[i]].x);
}

int main () {
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	read ();
	solve ();
	return 0;
}