#include <fstream>
using namespace std;
# define MAXIM 2000000
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,ns,mat[5000][5000],viz[50000],T[50000],C[50000],s;
void APM()
{
    int i,j,k,q,nr,minn;
    viz[1]=1;
    for(nr=2;nr<=n;nr++)
    {minn=MAXIM;


        for(i=1;i<=n;i++)
        {       k=0;
                q=0;
                //minn=MAXIM;

            for(j=1;j<=n;j++)
            {


                  if(viz[i]==1)
                    if(mat[i][j]!=0)
                      if(viz[j]==0)

                              if(mat[i][j]<minn)
                                {
                                minn=mat[i][j];
                                k=j;
                                q=i;
                                }

            //out<<k<<" "<<q<<" ";


            C[k]=minn;
            T[k]=q;
            viz[k]=1;

            }

        }


    }
}
int main()
{int a,b,c,x,i;
  in>>n>>m;
  for(i=1;i<=m;i++)
  {
      in>>a>>b>>c;
      mat[a][b]=c;
      mat[b][a]=c;
  }
in.close();
APM();
/*for(i=1;i<=n;i++)
    out<<T[i]<<" ";
out<<endl;
for(i=1;i<=n;i++)
        out<<C[i]<<" ";
*/
x=n-1;
s=0;
for(i=1;i<=n;i++)
    s=s+C[i];

out<<s<<endl;
out<<x<<endl;
for(i=2;i<=n;i++)
    out<<T[i]<<" "<<i<<endl;
  out.close();

    return 0;
}