#include <fstream>
#include <vector>
#include <queue>
#define NMAX 200002
#define INF 1000000

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");


struct Varf {int x; int c;};
struct Muchie
       {int x, y; int c;
        friend bool operator < (Muchie m1, Muchie m2);
       }; //x este varful; costul muchiei de la y la x este c
priority_queue<Muchie> H;
vector<Varf> G[NMAX];
int n, m, start=1, total;
bool uz[NMAX];
Muchie a[NMAX];
int cmin[NMAX];

bool operator < (Muchie m1, Muchie m2)
{
 return m1.c>m2.c;
}

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

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

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

void prim()
{int i, j, k, vf;
 Muchie m, mm;
 ///initializare
 uz[start]=1;
 for (i=1; i<=n; i++) cmin[i]=INF;
 cmin[start]=0;
 ///parcurg lista de adiacenta a varfului start
 for (i=0; i<G[start].size(); i++)
     {m.y=start; m.x=G[start][i].x; m.c=G[start][i].c;
      H.push(m);
      cmin[m.x]=m.c;
     }

 for (i=1; i<n; )
     {
      ///aflu minimul pentru varfurile neselectate
      m=H.top(); H.pop();
      if (uz[m.x]==0)
         {
          uz[m.x]=1;
          total+=m.c; a[i]=m;
          i++;
          ///actualizez eventual costurile minime catre vf neselectate
          ///parcurg lista de adiacenta a lui m.x
          vf=m.x;
          for (k=0; k<G[vf].size(); k++)
              if (uz[G[vf][k].x]==0 && //varf neselectat
                 cmin[G[vf][k].x]>G[vf][k].c)
                 {
                  mm.x=G[vf][k].x; mm.y=vf; mm.c=G[vf][k].c;
                  H.push(mm);
                  cmin[mm.x]=mm.c;
                 }
         }
    }
}

void afisare()
{int i;
 fout<<total<<'\n'<<n-1<<'\n';
 for (i=1; i<n; i++) fout<<a[i].x<<' '<<a[i].y<<'\n';
 fout.close();
}