#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];

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

 for (i=1; i<n; )
     {
      ///aflu minimul pentru varfurile neselectate
      m=H.top(); H.pop();
      if (uz[m.x]==0)
         {
         ///selectez varful pozminim
         uz[m.x]=1;
         total+=m.c; a[i]=m;
         i++;
         ///actualizez eventual costurile minime cartre 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
                 {
                  mm.x=G[vf][k].x; mm.y=vf; mm.c=G[vf][k].c;
                  H.push(mm);
                 }
     }
   }
}

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