#include<fstream.h>
#define NMAX 200005
#define MMAX 400005
#define INF 50000
#include<list>
using namespace std;
typedef list<long> LI;
typedef LI::iterator IT;
LI c[NMAX],a[NMAX];
long s,n,m,r,p[NMAX], cmin[NMAX],x[NMAX];
void cit()
{ifstream fin("apm.in");
  fin>>n>>m;
  long i,x,y,cost;
  for(i=1;i<=m;++i)
	  {fin>>x>>y>>cost;
       a[x].push_back(y);
	   c[x].push_back(cost);
	   a[y].push_back(x);
	   c[y].push_back(cost);
	  }
   fin.close();
}
void solve()
{long i,j,min,vfmin;
 for(i=1;i<=n;++i)
	 cmin[i]=INF;
  r=1;
  for(i=1;i<=n;++i)
	  p[i]=1;
  p[r]=0;
 IT pr,q;
	   for(pr=a[r].begin(),q=c[r].begin();pr!=a[r].end();++pr,++q)
		   if(cmin[*pr]>*q)
			   {cmin[*pr]=*q;
		        x[*pr]=r;
			   }
	for(j=1;j<=n-1;++j)
	 {min=INF;
		  for(i=1;i<=n;++i)
			if(p[i]&&cmin[i]<min)
			{min=cmin[i];
			 vfmin=i;
			}
	  p[vfmin]=0;
	  s+=min;
	   for(pr=a[vfmin].begin(),q=c[vfmin].begin();pr!=a[vfmin].end();++pr,++q)
		   if(cmin[*pr]>*q&&p[*pr])
		    {cmin[*pr]=*q;x[*pr]=vfmin;}
	 }
}
void afis()
{long i,t;
 ofstream fout("apm.out");
  fout<<s<<'\n'<<n-1<<'\n';
   t=r;
    for(i=1;i<=n;++i)
	 if(i!=r) 
	  fout<<i<<" "<<x[i]<<'\n';
  fout.close();
}
int main()
{cit();
 solve();
 afis();
 return 0;
}