#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#define NMAX 666013
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 elim(unsigned a, unsigned b)
{
     queue<muchie> _aux;
     muchie aux;
     while(G[a].top().vf!=b)
     {
        aux.vf=G[a].top().vf;
        aux.cost=G[a].top().cost;
        G[a].pop();
        _aux.push(aux);
     }
     G[a].pop();
     while(_aux.size()) G[a].push(_aux.front()), _aux.pop();
}

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();
     elim(aux.vf2, aux.vf1);
     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();
         elim(aux.vf2, aux.vf1);
         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;
}