#include <cstdio>
#include <algorithm>
using namespace std;

int n,m,h1,viz[200001],h[400001],muchie[400000][3];
int cost,muchii[400000][2];

struct nod
{
    int i;
    nod *u;
}*noduri[200001];

void urca(int k)
{
    while(k>1&&muchie[h[k]][2]<muchie[h[k>>1]][2])
    {
        swap(h[k],h[k>>1]);
        k>>=1;
    }
}

void coboara(int k)
{
    if(k<<1>h1) return;
    int j=k<<1;
    if(j+1<=h1) if(muchie[h[j]][2]>muchie[h[j+1]][2]) ++j;
    while(muchie[h[k]][2]>muchie[h[j]][2])
    {
        swap(h[k],h[j]);
        k=j;
        if(k<<1>h1) return;
        j=k<<1;
        if(j+1<=h1) if(muchie[h[j]][2]>muchie[h[j+1]][2]) ++j;
    }
}

void adauga(int x)
{
    h[++h1]=x;
    urca(h1);
}

void sterge(int k)
{
    h[k]=h[h1];
    --h1;
    coboara(k);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i;
    nod* nd;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;++i)
    {
        scanf("%d%d%d",&muchie[i][0],&muchie[i][1],&muchie[i][2]);
        nd=new nod;
        nd->u=noduri[muchie[i][0]];
        noduri[muchie[i][0]]=nd;
        nd->i=i;
        nd=new nod;
        nd->u=noduri[muchie[i][1]];
        noduri[muchie[i][1]]=nd;
        nd->i=i;
    }
    m=0;
    viz[1]=1;
    nd=noduri[1];
    while(nd)
    {
        adauga(nd->i);
        nd=nd->u;
    }
    --n;
    while(n)
    {
        i=0;
        while(!i)
        {
            if(!viz[muchie[h[1]][0]]) i=muchie[h[1]][0];
            else if(!viz[muchie[h[1]][1]]) i=muchie[h[1]][1];
                 else sterge(1);
        }
        --n;
        viz[i]=1;
        muchii[m][0]=muchie[h[1]][0];
        muchii[m++][1]=muchie[h[1]][1];
        cost+=muchie[h[1]][2];
        sterge(1);
        nd=noduri[i];
        while(nd)
        {
            if(!viz[muchie[nd->i][0]]||!viz[muchie[nd->i][1]]) adauga(nd->i);
            nd=nd->u;
        }
    }
    printf("%d\n%d\n",cost,m);
    for(i=0;i<m;++i) printf("%d %d\n",muchii[i][0],muchii[i][1]);
    return 0;
}