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