#include <fstream>
using namespace std;
ifstream d("apm.in");
ofstream o("apm.out");
int m,n,x,y,i,j,t,c[200002],s[200002],p[200002],n1,n2,k,minn;
short g[20000][20000],z;
int main()
{
  d>>n>>m;
  for (i=1;i<=m;i++) {d>>x>>y>>z; g[x][y]=g[y][x]=z;}
  s[1]=1;
  for (k=1;k<=n-1;k++)
    {
      n1=n2=-1; minn=10000;
      for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
          if (g[i][j]!=0)
            if ((s[i]==1)and(s[j]==0))
              if (g[i][j]<minn)
                {
                  minn=g[i][j];
                  n1=i;
                  n2=j;
                }
      s[n2]=1;
      p[n2]=n1;
      c[n2]=g[n1][n2];
      t+=c[n2];
    }
  o<<t<<'\n';
  o<<n-1<<'\n';
  for (i=2;i<=n;i++) o<<i<<' '<<p[i]<<'\n';
}