#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,j,k,m,viz[200005],a,b,aa[200005],bb[200005],rez;
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)
{
	if (viz[t]==t) return t;
	else return find(viz[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;
				j=max(find(v[i].x),find(v[i].y));
				viz[v[i].x]=viz[v[i].y]=j;
				rez++;
				aa[rez]=v[i].x;
				bb[rez]=v[i].y;
	}
	printf("%lld\n",rezz);
	printf("%d\n",rez);
	for (i=1;i<=rez;i++)printf("%d %d\n",bb[i],aa[i]);
	return 0;
}