#include <cstdio>
#include <vector>
#define NMAX 200001
#define MMAX 400001
using namespace std;
FILE* fin=fopen("apm.in","r");
FILE* fout=fopen("apm.out","w");
int h[NMAX],tata[NMAX],n,M,total;
struct muchie
{
    int x,y,c;
};
muchie m[MMAX],apm[NMAX];
void citire();
int Find(int x);
void Union(int x,int y);
void rezolvare();
void afisare();
void combheap(int poz);
void creareheap();
muchie extractmin();
int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}
void citire()
{
    int i;
    fscanf(fin,"%d %d",&n,&M);
    for (i=1; i<=M; i++)
        fscanf(fin,"%d %d %d",&m[i].x,&m[i].y,&m[i].c);
    creareheap();
}
void creareheap()
{
    int i;
    for (i=M/2; i>=1; i--)
        combheap(i);
}
void combheap(int poz)
{
    int f=2*poz;
    muchie aux;
    while (f<=M)
    {
        if (f+1<=M && m[f].c > m[f+1].c)
            f++;
        if (m[poz].c>m[f].c)
        {
            aux=m[poz];
            m[poz]=m[f];
            m[f]=aux;
            poz=f;
            f=2*f;
        }
        else f=M+1;
    }
}
muchie extractmin()
{
    muchie v=m[1];
    m[1]=m[M--];
    combheap(1);
    return v;
}
void rezolvare()
{
    int i,rx,ry;
    bool gasit;
    muchie e;
    for (i=1; i<=n-1; i++)
    {
        gasit=0;
        while (!gasit)
        {
            e=extractmin();
            rx=Find(e.x);
            ry=Find(e.y);
            if (rx!=ry)
            {
                gasit=1;
                Union(e.x,e.y);
                apm[i]=e;
                total+=e.c;
            }
        }
    }
}
int Find(int x)
{
    int rx=x,aux;
    while (tata[rx]) rx=tata[rx];
    while (tata[x])
    {
        aux=tata[x];
        tata[x]=rx;
        x=aux;
    }
    return rx;
}
void Union(int x,int y)
{
    int rx,ry;
    rx=Find(x);
    ry=Find(y);
    if (h[rx]>h[ry])
        tata[ry]=rx;
    else
    {
        if (h[rx]<h[ry]) tata[rx]=ry;
        else
        {
            tata[rx]=ry;
            h[ry]++;
        }
    }
}
void afisare()
{
    fprintf(fout,"%d\n",total);
    fprintf(fout,"%d\n",n-1);
    for (int i=1; i<=n-1; i++)
        fprintf(fout,"%d %d\n",apm[i].x,apm[i].y);
}