#include <fstream>
#define INF 1000000
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, start, costmin;
int cmin[1501];
int viz[1501], tata[1501];

void citire();
void prim();
void afisare();

struct muchie{int vf, cst;};
muchie c[1501][1501];

int main()
{
    citire();
    prim();
    afisare();
    return 0;
}

void citire()
{
    int i, m, x, y, cost, j;
    fin>>n>>m; start=1;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        //c[x][y]=c[y][x]=cost;
        c[x][++c[x][0].vf].vf=y; c[x][c[x][0].vf].cst=cost;
        c[y][++c[y][0].vf].vf=x; c[y][c[y][0].vf].cst=cost;
    }
    for(i=1;i<=n;i++)
    {
        cmin[i]=INF;
        tata[i]=start;
    }
    tata[start]=0; viz[start]=1; cmin[start]=0;
    for(i=1;i<=c[start][0].vf;i++)
        cmin[c[start][i].vf]=c[start][i].cst;
}

void prim()
{
    int vfmin, i, x, nrmin, neviz=n-1;
    while(neviz)
    {
        nrmin=INF;
        for(i=1;i<=n;i++)
            if(!viz[i]&&nrmin>cmin[i])
            {
                nrmin=cmin[i]; vfmin=i;
            }
            viz[vfmin]=1; neviz--;
            //fout<<vfmin<<' '<<tata[vfmin]<<'\n';
            costmin+=nrmin;
            for(x=1;x<=c[vfmin][0].vf;x++)
                    if(!viz[c[vfmin][x].vf]&&cmin[c[vfmin][x].vf]>c[vfmin][x].cst)
                    {
                        cmin[c[vfmin][x].vf]=c[vfmin][x].cst;
                        tata[c[vfmin][x].vf]=vfmin;
                    }
    }
}

void afisare()
{
    int i;
    fout<<costmin<<'\n'<<n-1<<'\n';
    for(i=n;i>1;i--)
        fout<<tata[i]<<' '<<i<<'\n';
}