#include <stdio.h>
#include <algorithm>
#include <bitset>

using namespace std;
FILE *f,*g;
int n,m,tata[200002],rang[200002],ss,arbore[400002][3],tot,x,y;
bitset <200002>fr;
typedef struct
{
    int n1,n2,c;
}pereche;
pereche v[400002];

bool cm(pereche p,pereche q)
{
    if(p.c>q.c)
        return (p.c<q.c);
}

void read()
{
    int i;
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;++i)
        fscanf(f,"%d %d %d",&v[i].n1,&v[i].n2,&v[i].c);
     sort(v+1,v+m+1,cm);
}

int multime(int nod)///determin multimea din care face parte nodul nod
{
    if(tata[nod]!=nod)///nu am ajuns la radacina, adica tatal nodului nu coincide cu nodul
        tata[nod]=multime(tata[nod]);///modificam parintele nodului cu radacina arborelui din care face parte
    return tata[nod];
}

void change(int x, int y)
{
    x=multime(x);
    y=multime(y);
    if(rang[x]<rang[y])
        tata[x]=y;
    else
        tata[y]=x;
    if(rang[x]==rang[y])
        ++rang[x];
}


void solve()
{
    for(int i=1;i<=n;++i)
        tata[i]=i,rang[i]=0;///initial tatal fiecarui nod va fi el insusi si rangul fiecarui nod va fi 0
    int cost;
    for(int i=1;i<=m;++i)
    {
        x=v[i].n1;
        y=v[i].n2;
        cost=v[i].c;
        if(multime(x)!=multime(y))///nu fac parte din aceiasi multime
        {
            change(x,y);
            ss+=cost;
            ++tot;
            arbore[tot][1]=x;
            arbore[tot][2]=y;
        }
    }

}

void write()
{
    fprintf(g,"%d\n",ss);
    fprintf(g,"%d\n",tot);
    for(int i=1;i<=tot;++i)
        fprintf(g,"%d %d\n",arbore[i][1],arbore[i][2]);
}

int main()
{
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    read();
    solve();
    write();
    fclose(f);
    fclose(g);
    return 0;
}