#include <fstream>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int Nmax=10000;
const int inf=99999999;
int n,mini,m,mat[Nmax][Nmax],d[Nmax],v[Nmax],cost[Nmax],t[Nmax],ok;

void apm(int ns)
{   int i,j,nod;
    for(i=1;i<=n;i++)
    {   d[i]=mat[ns][i];
        t[i]=ns;

    }
    v[ns]=1;

    ok=0;
    while(ok==0)
    {   mini=inf;
        for(i=1;i<=n;i++)
        {   if(v[i]==0)
                if(d[i]<mini)
                {   nod=i;
                    mini=d[i];

                }

        }
        v[nod]=1;
        if(mini==inf) ok=1;
        else
        for(i=1;i<=n;i++)
        {   if(v[i]==0)
                if(d[i]>mat[nod][i]+mini)
                {   d[i]=mat[nod][i]+mini;
                    cost[i]=mat[nod][i];
                    t[i]=nod;

                }

        }



    }

}
int main()
{
    int i,a,b,c,j;
    in>>n>>m;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    mat[i][j]=inf;
    for(i=1;i<=m;i++)
    {   in>>a>>b>>c;
        mat[a][b]=c;
        mat[b][a]=c;
    }
    apm(1);
    cost[1]=0;
    c=0;

    for(i=1;i<=n;i++)
       if(i!=1)
        c=c+mat[t[i]][i];

    out<<c<<"\n"<<n-1<<"\n";
    for(i=2;i<=n;i++)
    {
        out<<t[i]<<" "<<i<<"\n";

    }
    return 0;
}