#include<fstream>  
#include<bitset>  
#include<vector>  
#include<algorithm>  
#define NMAX 666013  
using namespace std;  
   
struct muchie{  
        unsigned vf1, vf2;  
        int cost;  
};  
  
vector<muchie> G, T;  
bitset<NMAX> viz;  
unsigned N, M;  
int s=0;  
ifstream f ("apm.in");  
ofstream g ("apm.out");  
 
bool cmp(const muchie& a, const muchie& b)  
{  
     return (a.cost<b.cost) ? true : false;  
}  

void read()  
{  
     f>>N>>M;  
     muchie aux;  
     for(unsigned i=0;i<M;i++)  
     {  
        f>>aux.vf1>>aux.vf2>>aux.cost;  
        G.push_back(aux);  
     }  
}  
  
bool test(unsigned a, unsigned b)  
{  
   return (viz[a]&&!viz[b])||(viz[b]&&!viz[a]) ? true : false;  
}  
  
void solve()  
{  
      sort(G.begin(), G.end(), cmp);  
      T.push_back(G[0]);  
      viz[G[0].vf1]=viz[G[0].vf2]=1;  
      s+=G[0].cost;  
      int min;  
      muchie aux;  
      unsigned k;  
      swap(G[0], G[G.size()-1]);  
      G.pop_back();  
      while(T.size()<N-1)  
      {  
         min=NMAX;  
         for(unsigned i=0;i<G.size();i++)  
            if( (G[i].cost<min) && (test(G[i].vf1, G[i].vf2)) ) min=G[i].cost, aux=G[i], k=i;  
         T.push_back(aux);  
         viz[aux.vf1]=viz[aux.vf2]=1;  
         s+=aux.cost;  
         swap(G[k], G[G.size()-1]);  
         G.pop_back();  
      }  
}  
   
void write()  
{  
        g<<s<<"\n"<<N-1<<"\n";  
        for(unsigned i=0;i<N-1;i++)  
        {  
           g<<T[i].vf1<<" "<<T[i].vf2<<"\n";  
        }  
}  
  
int main()  
{  
     read();  
     solve();  
     write();  
     return 0;  
}