#include <fstream>
#define NMAX 200002
#define MMAX 400002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
int tata[NMAX]; //vectorul de tati ai arborilor care reprezinta partitia
int inaltime[NMAX];
struct Muchie {int x, y, c;};
Muchie H[MMAX];
Muchie A[NMAX];

void Union(int i, int j);
int Find (int i);
void inserare(Muchie H[], int& n, int x);
void afisare();
void combinare(int poz);
Muchie ExtrageMin();
void creare();
void kruskal();

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

void kruskal()
{int nr, cx, cy;
 Muchie minim;
 //initial fiecare varf reprezinta o componenta conexa distincta
 for (nr=0; nr<n-1; )
     {
      minim=ExtrageMin();
      //verific daca extremitatile muchie de cost minim sunt in componente conexe diferite
      cx=Find(minim.x);
      cy=Find(minim.y);
      if (cx!=cy)
         {
          A[nr++]=minim;
          Union(cx,cy);
         }
     }
}

void Union(int i, int j)
//reuneste arborele cu radacina i cu arborele cu radacina j
{if (inaltime[i]<inaltime[j])
     tata[i]=j;
     else
     {
      tata[j]=i;
      if (inaltime[i]==inaltime[j]) inaltime[i]++;
     }
}
int Find (int i)
//determina radacina arborelui din care face parte i
{ int r=i, x, t;
  while (tata[r]) r=tata[r];
  //compresez drumul de la i la r
  x=i;
  while (x!=r)
        {
         t=tata[x];
         tata[x]=r;
         x=t;
        }
  return r;
}

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

void combinare(int poz)
{
 //nodul de pe pozitia poz se va combina cu minheapurile cu radacinile
 //2*poz si 2*poz+1 - acestea sunt deja corect construite
 Muchie x=H[poz];
 int tata=poz, fiu=2*poz;
 while (fiu<=m)
       {
        if (fiu+1<=m && H[fiu+1].c<H[fiu].c) fiu++;
        if (H[fiu].c<x.c)
           {H[tata]=H[fiu];
            tata=fiu;
            fiu=2*tata;
           }
           else break;
       }
H[tata]=x;
}

void creare()
//O(n)
{int i;
 fin>>n>>m;
 for (i=1; i<=m; i++) fin>>H[i].x>>H[i].y>>H[i].c;
 for (i=m/2; i>=1; i--)
     combinare(i);
}

Muchie ExtrageMin()
{Muchie minim=H[1];
 H[1]=H[m];
 m--;
 combinare(1);
 return minim;
}