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

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

struct muchie
{
   signed nod1, nod2, cost;
};

vector<muchie> G, T;
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>>aux.nod1>>aux.nod2>>aux.cost, G.push_back(aux);
}

void solve()
{
       sort(G.begin(), G.end(), Cost);  
       T.push_back(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.push_back(aux);  
          viz[aux.nod1]=viz[aux.nod2]=1;
          s+=aux.cost;
       }
}

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

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