#include<fstream>
#include<map>
#include<vector>
using namespace std;

typedef pair<double ,int > TPair;

int main()
{
ifstream in("apm.in");
ofstream out("apm.out");
multimap<double,int> E,H;
double aux;
double cost=0;
long long n,m,x,y;
multimap<double,int>::const_iterator its;
in>>n>>m;
 for(short i=0; i<m; i++)
	  { 
	          in>>x>>y>>aux;
			  E.insert(TPair(aux,(y-1)*n+x-1));
			  
	  }



H.clear();
vector<long long> C;
for(short i=0;i<n;i++) C.push_back(i);

while(H.size() < n-1)
{
short idx=0,uu,vv;
multimap<double,int>::iterator it;
it=E.begin();
uu=(it->second)/n; vv=(it->second)%n;
while(C[uu]==C[vv])
 {
   it++;
   uu=(it->second)/n;
   vv=(it->second)%n;
 }
 H.insert(TPair(it->first,it->second));
 cost+=it->first;
 E.erase(it);
 short mi=min(C[uu],C[vv]);
 short ma=max(C[uu],C[vv]);
 for(short i=0;i<n;i++)
	  if(C[i]==ma) C[i]=mi;
}
out<<cost<<endl;
out<<H.size()<<endl;
for(its=H.begin(); its!=H.end();its++)
 out<< (its->second)/n+1 <<" "<< its->second%n+1 <<endl;
return 0;
}