#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
FILE *f,*g;
int tata[200005],rang[200005];
struct Muchii
{
    int a,b,c;
};
struct Arbore
{
    int lin,col;
};
Arbore tt[400040];
Muchii vv[400040];
bool Criteriu(Muchii x, Muchii y)
{
    if(x.c!=y.c)return (x.c<y.c);
}
int VerMuc(int nod)
{
    if(tata[nod]!=nod)
        tata[nod]=VerMuc(tata[nod]);
    return tata[nod];
}
void Uneste(int aa, int bb)
{
    //if(aa==bb)
        //return;
    if(rang[aa]<rang[bb])
        tata[aa]=bb;
    else
        tata[bb]=aa;
    if(rang[aa]==rang[bb])
        ++rang[aa];
}
int main()
{
    f=fopen("apm.in","r");g=fopen("apm.out","w");
    int n,m,i,j,x,y,cos,sum=0,al,be;
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&x,&y,&cos);
        vv[i].a=x,vv[i].b=y,vv[i].c=cos;
        if(i<=n)
            tata[i]=i;
    }
    sort(vv+1,vv+1+m,Criteriu);
    cos=0;
    int aa,bb;
    for(i=1;i<=m;i++)
    {
        x=vv[i].a,y=vv[i].b;
        aa=VerMuc(x);
        bb=VerMuc(y);
        if(aa!=bb)
        {
            sum+=vv[i].c;
            Uneste(aa,bb);
            tt[++cos].lin=x;tt[cos].col=y;
        }
    }
    fprintf(g,"%d\n%d\n",sum,cos);
    for(i=1;i<=cos;i++)fprintf(g,"%d %d\n",tt[i].lin,tt[i].col);
    fclose(f),fclose(g);
    return 0;
}