#include <fstream>
#include <queue>
#define NMAX 200001

using namespace std;

struct Muchie
       {
       	int x, y;
       	int cost;
       	friend bool operator >(const Muchie&, const Muchie&);
       };
bool operator >(const Muchie& m1, const Muchie& m2)
{
 return m1.cost>m2.cost;
}

priority_queue<Muchie, vector<Muchie>, greater<Muchie> > H;
vector<Muchie> sol;
int tata[NMAX];
int h[NMAX];
int n;
int costmin;

void Citire();
void Afisare();
int Find (int);
void Union(int, int);

int main()
{int c1, c2;
 Muchie m;
 Citire();
 while (sol.size()<n-1)
       { m=H.top(); H.pop();
     	 c1=Find(m.x); c2=Find(m.y);
     	 if (c1!=c2) //m nu formeaza cicluri cu muchiile deja selectate
     	    { costmin+=m.cost; sol.push_back(m);
     	   	  Union(c1, c2);
     	    }
        }
 Afisare();
 return 0;
}

void Citire()
{Muchie m;
 int i, nrm;
 FILE * fin=fopen("kruskal.in", "r");
 fscanf(fin,"%d %d", &n, &nrm);
 for (i=0; i<nrm; i++)
     {
      fscanf(fin,"%d %d %d", &m.x, &m.y, &m.cost);
      H.push(m);
     }
}

void Afisare()
{FILE * fout=fopen("kruskal.out","w");
 fprintf(fout,"%d\n", costmin);
 fprintf(fout,"%d\n", n-1);
 for (int i=0; i<n-1; i++)
     fprintf(fout,"%d %d\n",sol[i].x,sol[i].y);
 fclose(fout);
}

int Find (int x)
{int r=x;
 //determinam radacina arborelui
 while (tata[r]) r=tata[r];
 //compresam drumul
 int y=x, aux;
 while (y!=r)
       { aux=tata[y]; tata[y]=r; y=aux; }
 return r;
}

void Union (int c1, int c2)
{
if (h[c1]>h[c2]) tata[c2]=c1;
   else
   {
   	tata[c1]=c2;
   	if (h[c1]==h[c2]) h[c2]++;
   }
}