#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,j,k,m,viz[200005],a,b,aa[200005],bb[200005],rez,r1,r2;
long long rezz;
struct nod
{
	int x;
	int y;
	int cost;
}v[200005];

int cmp(const nod a,const nod b)
{
	return a.cost<b.cost;
}

int find(int t)
{
	while(viz[t]!=t) t=viz[t];
	return t;
}

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",&v[i].x,&v[i].y,&v[i].cost);
	sort(v+1,v+m+1,cmp);
	for (i=1;i<=n;i++) viz[i]=i;
	for (i=1;i<=m;i++) if (find(v[i].x)!=find(v[i].y))
			{
				rezz=rezz+v[i].cost;
				if (v[i].x>v[i].y) viz[v[i].y]=v[i].x;else viz[v[i].x]=v[i].y;
				rez++;
				aa[rez]=v[i].x;
				bb[rez]=v[i].y;
				if (rez==n-1) break;
	}
	printf("%lld\n",rezz);
	printf("%d\n",rez);
	for (i=1;i<=n-1;i++)printf("%d %d\n",bb[i],aa[i]);
	return 0;
}