#include <cstdio>
#include <algorithm>

using namespace std;
FILE *f,*g;

struct name
{
    int a,b,c;
}v[200002];

bool how(name A, name B)
{
    return (A.c<B.c);
}
int tata[200002],rang[200002];
struct
{
    int aa,bb;
}sol[200002];

int multime(int nod)
{
    int rad=nod;
    while(rad!=tata[rad])
        rad=tata[rad];
    return rad;
}
void unite(int tatax, int tatay)
{
    if(rang[tatax]<rang[tatay])
        tata[tatax]=tatay;
    else
        tata[tatay]=tatax;
    if(rang[tatax]==rang[tatay])
        ++rang[tatax];
}
int main()
{
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    int m,n,x,y,mx,my,ss=0,cost=0;
    fscanf(f,"%d %d",&n,&m);
    for(int i=1;i<=m;++i)
        fscanf(f,"%d %d %d",&v[i].a,&v[i].b,&v[i].c);
    sort(v+1,v+m+1,how);
    for(int i=1;i<=n;++i) tata[i]=i;
    for(int i=1;i<=m;++i)
    {
        x=v[i].a;
        y=v[i].b;
        mx=multime(x);
        my=multime(y);
        if(mx!=my)
        {
            unite(mx,my);
            cost+=v[i].c;
            sol[++ss].aa=x;
            sol[ss].bb=y;
        }
    }
    fprintf(g,"%d\n%d\n",cost,ss);
    for(int i=1;i<=n;++i)
        fprintf(g,"%d %d\n",sol[i].aa,sol[i].bb);

    fclose(f);
    fclose(g);
    return 0;
}