#include<fstream>
#include<algorithm>
#define dim 400009
using namespace std;
int n,m,t[dim],nrc,rg[dim],ales[dim],cost,i,k;
struct muchie
{
    int x,y,c;
};
muchie l[dim];
int cmp(muchie a,muchie b)
{
    return a.c<b.c;
}
int rad(int x)
{
    int r=x,y;
    while(t[r]!=r)
	r=t[r];

    while(t[x]!=x)
    {
        y=t[x];
        t[x]=r;
        x=y;
    }
    return r;
}
int uneste(int x,int y)
{
    nrc--;
    if(rg[rad(x)]>rg[rad(y)])
	t[rad(y)]=x;
    else
	t[rad(x)]=y;
    if (rg[rad(x)]==rg[rad(y)])
	rg[rad(y)]++;
    return 0;
}
int main()
{
	freopen ("apm.in","r",stdin);
	freopen ("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
	scanf("%d%d%d",&l[i].x,&l[i].y,&l[i].c);
    nrc=n;
    for(int i=1;i<=n;i++)
	{
		t[i]=i;
		rg[i]=1;
    }
    i=1;
    sort(l+1,l+m+1,cmp);
    /*for(int i=1;i<=m;i++)
	printf("%d %d %d\n",l[i].x,l[i].y,l[i].c);
	printf("\n");*/
    while(nrc>1)
    {
        while(rad(l[i].x)==rad(l[i].y))
		i++;
        uneste(l[i].x,l[i].y);
        ales[++ales[0]]=i;
        cost+=l[i].c;
        i++;
    }
    printf("%d\n%d\n",cost,ales[0]);
    for(int i=1;i<=ales[0];i++)
	{
	printf("%d %d\n",l[ales[i]].x,l[ales[i]].y);
	}
}