#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define maxn 200005
#define infinit 1<<30

struct graf
    {   int nod,cost;   };
graf *a[maxn];
int grad[maxn];
int h[maxn],poz[maxn],c[maxn],parinte[maxn];
int n,m,vf,aam;

    void citire(void)
    {   FILE *fin=fopen("apm.in","r");
        int x,y,c;
        fscanf(fin,"%d%d",&n,&m);
        for(;m;m--)
        {   fscanf(fin,"%d%d%d",&x,&y,&c);
            a[x]=(graf*)realloc(a[x],(grad[x]+1)*sizeof(graf));
            a[x][grad[x]].cost=c; a[x][grad[x]].nod=y;
            grad[x]++;
            a[y]=(graf*)realloc(a[y],(grad[y]+1)*sizeof(graf));
            a[y][grad[y]].cost=c; a[y][grad[y]].nod=x;
            grad[y]++;
        }
        fclose(fin);
    }

    void upheap(int fiu)
    {   int v=h[fiu],tata=fiu>>1;
        while(tata && c[ h[tata] ]>c[v])
        {   h[fiu]=h[tata]; poz[ h[tata] ]=fiu;
            fiu=tata; tata=fiu>>1;
        }
        h[fiu]=v; poz[v]=fiu;
    }

    void downheap(int tata)
    {   int v=h[tata],fiu=tata<<1;
        while(fiu<=vf)
        {   if(fiu<vf && c[ h[fiu] ]>c[ h[fiu+1] ]) fiu++;
            if(c[ h[fiu] ]<c[v])
            {   h[tata]=h[fiu]; poz[ h[fiu] ]=tata;
                tata=fiu; fiu=tata<<1;
            }
            else fiu=vf+1;
        }
        h[tata]=v; poz[v]=tata;
    }

    int extrage_min(void)
    {   int r=h[1];
        h[1]=h[vf--];
        downheap(1);
        return r;
    }

    void prim(int sursa)
    {   int k,min;
        for(k=1;k<=n;k++) h[k]=k, c[k]=infinit, poz[k]=k;
        c[sursa]=0; parinte[sursa]=0;
        vf=n;
        while(vf)
        {   min=extrage_min(); aam+=c[min]; poz[min]=0;
            for(k=0;k<grad[min];k++)
                if(poz[ a[min][k].nod ] && c[ h[ poz[ a[min][k].nod] ] ]> a[min][k].cost)
                {   c[ h[ poz[ a[min][k].nod] ] ]=a[min][k].cost;
                    parinte[ a[min][k].nod ]=min; upheap(poz[ a[min][k].nod ]);
                }
        }
    }

    void afisare(void)
    {   FILE *fout=fopen("apm.out","w");
        fprintf(fout,"%d\n%d\n",aam,n-1);
        for(int k=2;k<=n;k++) fprintf(fout,"%d %d\n",parinte[k],k);
        fclose(fout);
    }

int main(void)
{   citire();
    prim(1);
    afisare();
    return 0;
}