#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;
     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;
        G.erase(G.begin()+k);
     }
}

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;
}