#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct apm
{
		int x,y,c;
};

struct qq
{
		int xx,yy;
};

apm f[4001];
qq rez[2001];
int t[4001];
int h[4001];
int px,py,i,cost,num,n,m;

bool cmp(apm a,apm b)
{
		return a.c<b.c;
}

int initset(int k)
{
		while(t[k]!=k)
			k=t[k];
		return k;
}

void unionset(int k,int q)
{
		if(h[k]==h[q])
			{
				++h[k];
				t[q]=k;
			}
		else
			if(h[k]>h[q])
				t[q]=k;
			else
				t[k]=q;
}

int main()
{
		freopen("apm.in","r",stdin);
		freopen("apm.out","w",stdout);
		scanf("%d%d",&n,&m);
		for(i=1;i<=m;++i)
			scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].c);
		sort(f+1,f+m+1,cmp);
		for(i=1;i<=n;++i)
			{
				t[i]=i;
				h[i]=1;
			}
		for(i=1;i<=m;++i)
			{
				px=initset(f[i].x);
				py=initset(f[i].y);
				if(px!=py)
					{
						unionset(px,py);
						cost+=f[i].c;
						rez[++num].xx=f[i].x;
						rez[num].yy=f[i].y;
					}
			}
		printf("%d\n",cost);
		printf("%d\n",num);
		for(i=1;i<=num;++i)
			printf("%d %d\n",rez[i].xx,rez[i].yy);
		return 0;
}