#include<fstream.h>
#define NMAX 200005
#define MMAX 400005
#define INF 50000
#include<list>
#include<iostream.h>
#include<map>
using namespace std;
typedef list<long> LI;
typedef LI::iterator IT;
LI c[NMAX],a[NMAX];
multimap<long,long> H;
multimap<long,long>::iterator it;
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=3;
  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;
		        H.insert(pair<long,long>(*q,*pr));
		        x[*pr]=r;
			   }
	for(j=1;j<=n-1;++j)
	 {min=INF;
	  it=H.begin();
	  min=it->first;
	  vfmin=it->second;
	  p[vfmin]=0;
	  s+=min;
	  H.erase(it);
	   for(pr=a[vfmin].begin(),q=c[vfmin].begin();pr!=a[vfmin].end();++pr,++q)
		   if(cmin[*pr]>*q&&p[*pr])
		    {it=H.lower_bound(cmin[*pr]);
		     for(;it->first==cmin[*pr];++it)
				 if(it->second==*pr)
					 break;
			 if(it!=H.end()) 	 
			  H.erase(it);
			 H.insert(make_pair(*q,*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;
}