#include <fstream>
#define nrmax 200001
#define inf 1001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int a[nrmax][nrmax],p[nrmax],z[nrmax];
int cmin[nrmax],costmin;
int n,m,vfmin,nrv;

void citire()
{
    int i,j,x,y,c;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(i==j) a[i][j]=0;
        else a[i][j]=inf;

    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        a[x][y]=a[y][x]=c;
    }
    for(i=1;i<=n;i++)
    {
        cmin[i]=a[1][i];
        p[i]=1; z[i]=1;
    }
    z[1]=0; p[1]=0; nrv=n-1;
    fin.close();
}

void afisare()
{
    int i,cost=0;
    for(i=1;i<=n;i++)
        cost+=a[i][p[i]];

    fout<<cost<<'\n'<<n-1<<'\n';

    for(i=1;i<=n;i++)
       if(i!=1) fout<<p[i]<<' '<<i<<'\n';

}

int main()
{
    int i;
    citire();
    while(nrv)
    {
        costmin=inf;
        for(i=1;i<=n;i++)
            if(z[i]&&costmin>cmin[i])
        {
            costmin=cmin[i];
            vfmin=i;
        }
        z[vfmin]=0;
        nrv--;
        for(i=1;i<=n;i++)
            if(z[i]&&a[i][vfmin]<cmin[i])
        {
            p[i]=vfmin;
            cmin[i]=a[i][vfmin];
        }
    }
    afisare();
}