#include <fstream>
#include <queue>

#define NMAX 200002
#define MMAX 400002

using namespace std;

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

struct muchie
{
 int x, y, c;
 friend bool operator < (muchie a, muchie b);
};

int n, m;
int tata[NMAX], h[NMAX]; //vector de tati respectiv vector pentru inaltimile arborilor

muchie apm[NMAX];
int costmin = 0;

priority_queue<muchie> H;

bool operator < (muchie a, muchie b)
{
    return a.c > b.c;
}

int Find(int x); //returneaza radacina subarborelui din care face parte x
void Union(int x, int y); //reuneste arborele in care se afla x cu arborele in care se afla y
void citire();
void kruskal();
void afisare();

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

void citire()
{
 int i;
 muchie aux;
 fin>>n>>m;
 for(i = 0; i < m; i++)
 {
     fin>>aux.x>>aux.y>>aux.c;
     H.push(aux);
 }
}

void kruskal()
{
 int nrsel = 0, rx, ry;
 muchie aux;
 //vectorul h si tata sunt deja initializati corespunzator (cu 0)
 while(nrsel < n - 1)
 {
      aux = H.top(); H.pop();
      rx = Find(aux.x);
      ry = Find(aux.y);
      if(rx != ry)
      {
         costmin += aux.c;
         apm[++nrsel] = aux;
         Union(rx, ry);
      }
 }

}

void afisare()
{
 int i;
 fout<<costmin<<'\n'<<n - 1<<'\n';
 for(i = 1; i < n; i++) //am n - 1 muchii in apm
    fout<<apm[i].x<<' '<<apm[i].y<<'\n';
}

int Find(int x)
{
 int y, rx;
 rx = x;
 while(tata[rx]) rx = tata[rx];
 //rx este radacina arborelui
 //compresez drumul de la x la rx;
 //fiecare nod de pe acest drum devine fiu al lui rx
 while(tata[x] && tata[x] != rx)
 {
      y = tata[x];
      tata[x] = rx;
      x = y;
 }
 return rx;
}

void Union(int x, int y)
{
 int rx = Find(x);
 int ry = Find(y);
 if(h[rx] < h[ry]) //rx devine fiul lui ry
   tata[rx] = ry;
   else
      if(h[ry] < h[rx]) //ry devine fiul lui rx
         tata[ry] = rx;
      else //egalitate
      {
         tata[ry] = rx;
         h[rx]++;
      }
}