#include <cstdio>
#include <vector>
#include <algorithm>

#define MAX 200001

using namespace std;

int n,m,val[400001],poz[MAX],lng,i,j,poz1,poz2,viz[MAX],k,tata[MAX],suma,x;

struct str
{
    int nod,ind;
};

str aux,h[MAX];
vector <str> G[MAX];

void up(int ind)
{
    if(ind>1 && val[h[ind].ind]<val[h[ind/2].ind])
    {
        swap(h[ind],h[ind/2]);
        swap(poz[h[ind].nod],poz[h[ind/2].nod]);
        up(ind/2);
    }
}

void down(int ind)
{
    if(ind*2<lng)
    {
        if(val[h[ind*2].ind]<val[h[ind*2+1].ind] && val[h[ind].ind]>val[h[ind*2].ind])
        {
            swap(h[ind],h[ind*2]);
            swap(poz[h[ind].nod],poz[h[ind*2].nod]);
            down(ind*2);
        }
        if(val[h[ind*2].ind]>=val[h[ind*2+1].ind] && val[h[ind].ind]>val[h[ind*2+1].ind])
        {
            swap(h[ind],h[ind*2+1]);
            swap(poz[h[ind].nod],poz[h[ind*2+1].nod]);
            down(ind*2+1);
        }
    }
    if(ind*2==lng && val[h[ind].ind]>val[h[ind*2].ind])
    {
        swap(h[ind],h[ind*2]);
        swap(poz[h[ind].nod],poz[h[ind*2].nod]);
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d %d",&n,&m);

    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d",&poz1, &poz2, &val[i]);
        aux.nod=poz2;
        aux.ind=i;
        G[poz1].push_back(aux);
        aux.nod=poz1;
        G[poz2].push_back(aux);
    }

    viz[1]=1;
    x=1;



    for(i=1; i<=n-1; i++)
    {
        k=G[x].size();
        for(j=0; j<k; j++)
        {
            if(!viz[G[x][j].nod] && !poz[G[x][j].nod])
            {
                lng++;
                poz[G[x][j].nod]=lng;
                h[lng].nod=G[x][j].nod;
                h[lng].ind=G[x][j].ind;
                tata[G[x][j].nod]=x;
                up(lng);
            }else
            if(!viz[G[x][j].nod] && val[G[x][j].ind] < val[h[poz[G[x][j].nod]].ind])
            {
                h[poz[G[x][j].nod]].ind=G[x][j].ind;
                up(poz[G[x][j].nod]);
                tata[G[x][j].nod]=x;
            }
        }

        viz[h[1].nod]=1;
        suma+=val[h[1].ind];
        x=h[1].nod;

        swap(h[1],h[lng]);
        swap(poz[h[1].nod], poz[h[lng].nod]);
        lng--;
        down(1);
    }



    printf("%d\n%d\n",suma,n-1);
    for(i=2; i<=n; i++) printf("%d %d\n",tata[i], i);

}