#include<fstream>
#include<bitset>
#include<algorithm>
#define NMAX 6660666
using namespace std;

ifstream f ("apm.in");
ofstream g ("apm2.out");

struct muchie
{
   int nod1, nod2, cost;
}G[400004], T[200002];

bitset<NMAX> viz;
int N, M, i, s=0;

bool Cost(const muchie& a, const muchie& b)
{
     return (a.cost>b.cost)?false:true;
}

void read()
{
     muchie aux;
     f>>N>>M;
     for(i=0;i<M;i++) f>>G[i].nod1>>G[i].nod2>>G[i].cost;
}

void solve()
{
       sort(G, G+M, Cost);  
       int nr=0;
       T[0]=G[0];
       s+=T[0].cost;
       viz[G[0].nod1]=viz[G[0].nod2]=1;
       while(viz.count()!=N)
       {
          muchie aux;
          aux.nod1=aux.nod2=aux.cost=NMAX;
          for(i=1;i<M;i++)
            if((G[i].cost<aux.cost)&&((viz[G[i].nod1]&&!viz[G[i].nod2])||(viz[G[i].nod2]&&!viz[G[i].nod1]))) aux=G[i];
          T[++nr]=aux; 
          viz[aux.nod1]=viz[aux.nod2]=1;
          s+=aux.cost;
       }
}

void write()
{
     g<<s<<"\n"<<N-1<<"\n";
     for(i=0;i<N-1;i++) g<<T[i].nod2<<" "<<T[i].nod1<<"\n";
}

int main()
{
    read();
    solve();
    write();
    return 0;
}