#include <fstream>
#define Infinit 100000000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,start,val;
int viz[10001],cmin[10001],tata[10001];
int v[10001],ct;

struct muchie{int vf, c;} G[10001][10001];

void citire();
void init();
void prim();
int detmin(int v[101],int &val);
void afisare();

int main()
{
    citire();
    init();
    prim();
    afisare();
    fout.close();
    return 0;
}

void citire()
{
    int i,x,y,cost,j;
    fin>>n>>m;
    start=1;
    for(i=1;i<=n;i++)
        cmin[i]=Infinit;

    cmin[start]=0;
    for(i=1;i<=m;i++)
        {
            fin>>x>>y>>cost;
            G[x][0].vf++;
            G[x][G[x][0].vf].c=cost; G[x][G[x][0].vf].vf=y;

            G[y][0].vf++;
            G[y][G[y][0].vf].c=cost; G[y][G[y][0].vf].vf=x;
        }
}

void init()
{
    int i;
    viz[start]=1;
    for(i=1;i<=G[start][0].vf;i++) cmin[G[start][i].vf]=G[start][i].c;

     for(i=1;i<=n;i++)
        if(i!=start) tata[i]=start;
}

void prim()
{
    int i,vrf,nrv=n,j;
    for(i=1;i<n;i++)
    {
            val=Infinit;
            vrf=detmin(cmin,val);
            viz[vrf]=1;

            //fout<<vf<<' '<<tata[vf]<<'\n';
            ct+=val;
            for(j=1;j<=G[vrf][0].vf;j++)
                if(viz[G[vrf][j].vf]==0&&cmin[G[vrf][j].vf]>G[vrf][j].c)
                {
                    cmin[G[vrf][j].vf]=G[vrf][j].c;
                    ct+=cmin[j];
                    tata[G[vrf][j].vf]=vrf;
                }


    }
}

int detmin(int v[101],int &val)
{
    int i,ind=0;
    for(i=1;i<=n;i++)
        if(cmin[i]<val&&viz[i]==0)
            {
                val=cmin[i]; ind=i;
            }
    return ind;
}

void afisare()
{
    int i,ctf=0;
    for(i=1;i<=n;i++)
        ctf+=cmin[i];
    fout<<ct<<'\n';
    fout<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<tata[i]<<' '<<i<<'\n';
}