#include <cstdio>
using namespace std;

int n,h=0,heap[200001][2],poz[200001],d[200001];
int m,dist=0,muchii[200000][2];

struct noduri
{
    int c,v;
    noduri *u;
}*nod[200001];

/*<implementare HEAP>*/
void urca(int x)
{
    int aux=heap[x][0],aux1=heap[x][1];
    while(x>1&&d[heap[x>>1][0]]>d[aux])
    {
        heap[x][0]=heap[x>>1][0];
        heap[x][1]=heap[x>>1][1];
        poz[heap[x][0]]=x;
        x>>=1;
    }
    heap[x][0]=aux;
    heap[x][1]=aux1;
    poz[heap[x][0]]=x;
}

void coboara(int x)
{
    int y,aux;
    do
    {
        y=0;
        if(x<<1<=h)
        {
            y=x<<1;
            if(d[heap[y+1][0]]<d[heap[y][0]]&&y+1<=h) ++y;
            if(d[heap[y][0]]>d[heap[x][0]]) y=0;
        }
        if(y)
        {
            poz[heap[x][0]]=y;
            poz[heap[y][0]]=x;
            aux=heap[x][0];
            heap[x][0]=heap[y][0];
            heap[y][0]=aux;
            aux=heap[x][1];
            heap[x][1]=heap[y][1];
            heap[y][1]=aux;
            x=y;
        }
    }
    while(y);
}

void sterge(int x)
{
    poz[heap[x][0]]=-1;
    poz[heap[h][0]]=x;
    heap[x][0]=heap[h][0];
    heap[x][1]=heap[h--][1];
    coboara(x);
}

void adauga(int x,int y)
{
    heap[++h][0]=x;
    heap[h][1]=y;
    poz[x]=h;
    urca(h);
}
/*</implementare HEAP>*/

/*<citire>*/
void adaugavecin(int x,int y,int c)
{
    noduri* nod1=new noduri;
    nod1->u=nod[x];
    nod1->v=y;
    nod1->c=c;
    nod[x]=nod1;
}

void read()
{
    freopen("apm.in","r",stdin);
    scanf("%d%d",&n,&m);
    int x,y,c;
    while(m)
    {
        --m;
        scanf("%d%d%d",&x,&y,&c);
        c+=10000;
        adaugavecin(x,y,c);
        adaugavecin(y,x,c);
    }
}
/*</citire>*/

void prim()
{
    poz[1]=-1;
    int x=1;
    --n;
    while(n)
    {
        while(nod[x])
        {
            if(!poz[nod[x]->v])
            {
                d[nod[x]->v]=nod[x]->c;
                adauga(nod[x]->v,x);
            }
            else
            {
                if(poz[nod[x]->v]!=-1&&d[nod[x]->v]>nod[x]->c)
                {
                    d[nod[x]->v]=nod[x]->c;
                    heap[poz[nod[x]->v]][1]=x;
                    urca(poz[nod[x]->v]);
                }
            }
            nod[x]=nod[x]->u;
        }
        muchii[m][1]=heap[1][0];
        muchii[m++][0]=heap[1][1];
        dist+=d[heap[1][0]]-10000;
        x=heap[1][0];
        sterge(1);
        --n;
    }
}

int main()
{
    read();
    prim();
    freopen("apm.out","w",stdout);
    printf("%d\n%d\n",dist,m);
    for(int i=0;i<m;++i)
    {
        printf("%d %d\n",muchii[i][0],muchii[i][1]);
    }
    return 0;
}