#include <iostream>
#include <fstream>
#include <utility>

using namespace std;


int main()
{
   ifstream f("apm.in");

   int n,m,x,y,c,total=0,k=1,min;
   pair <int,int> *p,*q;
   int *cost;
   bool *viz;

   f>>n>>m;


   p=new pair<int,int>[m];
   q=new pair<int,int>[n-1];
   cost=new int[m];
   viz=new bool[n];

   for(int i=0;i<n;i++) viz[i]=0;


   for(int i=0;i<m;i++)
   {
       f>>x>>y>>c;
       p[i]=make_pair(x,y);
       cost[i]=c;
   }

   viz[0]=1;int poz; x=0;

   while(k<n)
   {
       min=1000;
       for(int i=0;i<m;i++)
       if(cost[i]<min && ( (viz[p[i].first-1] && !viz[p[i].second-1]) ||(!viz[p[i].first-1] && viz[p[i].second-1]) ) )
       {
           min=cost[i];
           poz=i;
       }

       k++; total+=min;
       if(!viz[p[poz].second-1]) viz[p[poz].second-1]=1;
       else if(!viz[p[poz].first-1]) viz[p[poz].first-1]=1;

       q[x++]=make_pair(p[poz].first,p[poz].second);
   }

  ofstream g("apm.out");
  g<<total<<endl<<n-1<<endl;
  for(int i=0;i<n-1;i++) g<<q[i].first<<" "<<q[i].second<<endl;
   return 0;
}