#include <fstream>
#include <vector>
#include <queue>
#define NMAX 200002
#define INF 1000000000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct varf {
     int vf, c;
     friend bool operator >(const varf & vf1, const varf & vf2);
     };

bool operator >(const varf & vf1, const varf & vf2)
{
 return vf1.c>vf2.c;
}
priority_queue<varf, vector<varf>, greater<varf> > H;

int n;
vector <varf> G[NMAX];
int cost_apm;
int cmin[NMAX]; //cmin[x] costul minim de la varful de start la x, pe un lant care trece doar prin vf selectate
int prec[NMAX]; //prec[x]=vf adiacent cu x atunci cand il selectez pe x in apm
int uz[NMAX]; //uz[x]=1 daca vf x a fost selectat in apm

void citire();
void prim(int);
void afisare();

int main()
{citire();
 prim(1);
 afisare();
 return 0;
}

void citire()
{int i, m, x, y, cost;
 varf v;
 fin>>n>>m;
 for (i=0; i<m; i++)
     {
      fin>>x>>y>>cost;
      v.vf=y; v.c=cost;
      G[x].push_back(v);
      v.vf=x;
      G[y].push_back(v);
     }
}

void prim(int start)
{int x, i, j, minim, vfmin;
 varf aux;
 //initializare
 uz[start]=1;
 for (x=1; x<=n; x++)
     {prec[x]=start; cmin[x]=INF;}
 prec[start]=0; cmin[start]=0;
 aux.vf=start; aux.c=0;

 //pt varfurile adiacente cu varful de start schimb cmin
 for (i=0; i<G[start].size(); i++)
     {cmin[G[start][i].vf]=G[start][i].c;
      aux.vf=G[start][i].vf; aux.c=G[start][i].c;
      H.push(aux);
     }
 //prim, selectam n-1 varfuri
 for (j=1; j<n; )
     {//aleg un varf x cum cmin[x] minim care nu a mai fost deja selectat
      aux=H.top(); //O(1)
      vfmin=aux.vf; minim=aux.c;
      H.pop(); //O(log n)
      if (!uz[vfmin])
          {//selectez pe vfmin
          uz[vfmin]=1; cost_apm+=minim;
          //optimizez eventual cmin pentru varfurile neselectate adiacente cu vfmin
          for (i=0; i<G[vfmin].size(); i++)
              if (!uz[G[vfmin][i].vf] && cmin[G[vfmin][i].vf] > G[vfmin][i].c)
                 {cmin[G[vfmin][i].vf] = G[vfmin][i].c;
                  prec[G[vfmin][i].vf]=vfmin;
                  aux.vf=G[vfmin][i].vf;
                  aux.c=cmin[G[vfmin][i].vf];
                  H.push(aux);
                 }
          j++;
          }
     }
}

 void afisare()
{int x;
 fout<<cost_apm<<'\n'<<n-1<<'\n';
 for (x=1; x<=n; x++)
     if (prec[x])
        fout<<x<<' '<<prec[x]<<'\n';
}