#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,**a,*cmin,*p,*z,x,y,c,MAXX=10000,MINN,start=1,nrv,vfmin,cost;
int main()
{
    f>>n>>m;
    a=new int*[n+1];
    for(int i=0;i<=n;i++)
        a[i]=new int[n+1]{0};
    cmin=new int[n+1]{0};
    p=new int[n+1]{0};
    z=new int[n+1]{0};
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            a[i][j]=MAXX;
    nrv=n-1;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        a[x][y]=a[y][x]=c;
    }
    for(int i=1; i<=n; i++)
    {
        a[i][i]=0;
        p[i]=start;
        cmin[i]=a[start][i];
    }
    z[start]=1;
    p[start]=0;
    while(nrv)
    {
        MINN=MAXX;
        for(int i=1; i<=n; i++)
            if(!z[i]&&MINN>cmin[i])
            {
                MINN=cmin[i];
                vfmin=i;
            }
        z[vfmin]=1;
        for(int i=1; i<=n; i++)
            if(!z[i]&&a[i][vfmin]<cmin[i])
            {
                p[i]=vfmin;
                cmin[i]=a[i][vfmin];
            }
        nrv--;
    }
    for(int i=1; i<=n; i++)
    {
        if(i!=start)
            cost+=a[i][p[i]];
    }
    g<<cost<<'\n'<<n-1<<'\n';
    for(int i=1; i<=n; i++)
    {
        if(i!=start)
            g<<i<<" "<<p[i]<<'\n';
    }
    return 0;
}