#include <fstream>
#include <queue>
#include <functional>
#define NMAX 200001
#define MMAX 400001

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
      {
       int x, y, c;
       friend bool operator> (muchie a, muchie b);
      };

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

priority_queue<muchie, vector<muchie>, greater<muchie> > H;
vector<muchie> A; //apm
int cmin;//costul apm-ului

int n, m;
int tata[NMAX];
int h[NMAX]; //h[i]=inaltimea arborelui cu radacina i

int Find (int x)
{int rad=x, y;
while (tata[rad])
       rad=tata[rad];
//compresia drumului
if (rad!=x)
    {y=tata[x];
     while (y!=rad)
           {
            tata[x]=rad;
            x=y;
            y=tata[x];
           }
    }
return rad;
}

void Union(int x, int y)
{int i, j;
 i=Find(x); j=Find(y);
 if (i!=j)
    if (h[i]<h[j])
      tata[i]=j;
      else
      if (h[j]<h[i])
         tata[j]=i;
         else
        {tata[i]=j;
         h[j]++;
        }
}

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()
{muchie aux;
 int i, j;
 while (A.size()<n-1)
       {
         aux=H.top();
         H.pop();
         i=Find(aux.x);
         j=Find(aux.y);
         if (i!=j)
             {
              A.push_back(aux);
              cmin+=aux.c;
              Union(i,j);
             }
       }
}

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