#include <fstream>
#define NMAX 20004
#define pinf 1000000

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct nod{int nr,c;nod*urm;};
typedef nod*Lista;
Lista lis[NMAX];

long cmin[NMAX],prec[NMAX],M[NMAX];int n,m,start;

void read();
void inserare(Lista&,int,int);
void solve();
void write();

int main()
{
    read();
    solve();
    write();
    cin.close();cout.close();
    return 0;
}

void read()
{
    int i,x,y,c,j,mn=pinf;
    cin>>n>>m;
    for (i=1;i<=n;i++)
        lis[i]=NULL;
    for (i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        //if (C[x][y]!=0) cout<<x<<' '<<y<<'\n';
        inserare(lis[x],y,c);
        inserare(lis[y],x,c);
        if (mn>c)
        {
            mn=c;
            start=x;
        }
    }
}

void inserare(Lista&prim,int nr,int c)
{
    Lista aux;
    aux=new nod;
    aux->nr=nr;
    aux->c=c;
    aux->urm=prim;
    prim=aux;
}

void solve()
{
    int i,j,x,mn;Lista aux;
    M[start]=1;
    aux=lis[start];
    for (i=1;i<=n;i++)
    {
        cmin[i]=pinf;
        prec[i]=start;
    }
    while (aux!=NULL)
    {
        if (aux->c < cmin[aux->nr])
            cmin[aux->nr]=aux->c;
        aux=aux->urm;
    }

    prec[start]=0;
    cmin[start]=0;
    for (i=1;i<n;i++)
    {
        mn=pinf;x=0;
        for (j=1;j<=n;j++)
            if (cmin[j]<mn && M[j]==0)
        {
            mn=cmin[j];
            x=j;
        }
        M[x]=1;aux=lis[x];
        while (aux!=NULL)
        {
            if (aux->c < cmin[aux->nr] && M[aux->nr]==0)
            {
                cmin[aux->nr]=aux->c;
                prec[aux->nr]=x;
            }
            aux=aux->urm;
        }
    }
}

void write()
{
    int i;long long cost=0;
    for (i=1;i<=n;i++)
        cost+=cmin[i];
    cout<<cost<<'\n'<<n-1<<'\n';
    for (i=1;i<=n;i++)
        if (i!=start)
        cout<<i<<' '<<prec[i]<<'\n';
}