#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 c[1001][1001],v[10001],ct;

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++)
        for(j=1;j<=n;j++)
            if(i!=j) c[i][j]=Infinit;
    cmin[start]=0;
    for(i=1;i<=m;i++)
        {
            fin>>x>>y>>cost;
            c[x][y]=cost;
            c[y][x]=cost;
        }
}

void init()
{
    int i;
    viz[start]=1;
    for(i=1;i<=n;i++) cmin[i]=c[start][i];

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

void prim()
{
    int i,vf,nrv=n;
    while(nrv)
    {
            val=Infinit;
            vf=detmin(cmin,val); nrv--;
            viz[vf]=1;

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


    }
}

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;
    fout<<ct<<'\n';
    fout<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<tata[i]<<' '<<i<<'\n';
}