#include<fstream>  
#include<vector>  
#include<queue>  
#include<bitset>  
#include<algorithm>  
#define NMAX 77777  
using namespace std;  
  
ifstream f ("apm.in");  
ofstream g ("apm.out");  
  
struct muchie{  
       int cost;  
       unsigned vf;  
};  
  
struct muchie2{  
       unsigned vf1, vf2;  
};  
  
struct cmp   
{  
  bool operator() (const muchie& a, const muchie& b)   
  {  
      return a.cost > b.cost;  
  }  
};  
  
priority_queue<muchie ,vector<muchie>, cmp > G[NMAX];  
vector<muchie2> T;  
bitset<NMAX> viz;  
unsigned N, M;  
int s=0;  
  
void read()  
{  
     unsigned x, y, i;  
     int c;  
     muchie _aux;  
     f>>N>>M;  
     for(i=0;i<M;i++)  
     {  
        f>>x>>y>>c;  
        _aux.vf=y;  
        _aux.cost=c;  
        G[x].push(_aux);  
        _aux.vf=x;  
        G[y].push(_aux);  
     }  
}  
  
void solve()  
{  
     int min;  
     unsigned i;  
     muchie2 aux;  
     viz[1]=viz[G[1].top().vf]=1;  
     aux.vf1=1; aux.vf2=G[1].top().vf;  
     s+=G[1].top().cost;  
     G[1].pop();  
     G[aux.vf2].pop();
     T.push_back(aux);  
     while(T.size()<N-1)  
     {  
         min=NMAX;  
         for(i=1;i<=N;i++)  
           if( ( G[i].size() ) && ( G[i].top().cost<min ) && ( ( !viz[G[i].top().vf] && viz[i] ) || ( viz[G[i].top().vf] && !viz[i] ) ) ) min=G[i].top().cost, aux.vf1=i, aux.vf2=G[i].top().vf;  
         T.push_back(aux);  
         G[aux.vf1].pop();
         G[aux.vf2].pop();
         viz[aux.vf1]=viz[aux.vf2]=1;  
         s+=min;  
     }  
}  
  
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;  
}