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

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

struct muchie
      {int x, y;
       int cost;
       friend bool operator >(muchie, muchie);
      };

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

priority_queue<muchie, vector<muchie>, greater<muchie> > H;

int n;
int tata[NMAX];
int h[NMAX]; ///h[x] este inaltimea arborelui cu radacina x
int costmin;
muchie sel[NMAX];

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

int main()
{
 citire();    ///minHeapul este creat
 kruskal();
 afisare();
 return 0;
}

int Find(int x) ///returneaza radacina arborelui din care face parte x
{int rad, y;
 rad=x;
 while (tata[rad]) rad=tata[rad];
 ///compresez drumul
 while (tata[x])
       {y=tata[x]; tata[x]=rad; x=y;  }
 return rad;
}

void Union(int x, int y)
{int rx, ry;
 rx=Find(x); ry=Find(y);
 if (h[rx]>h[ry])
    tata[ry]=rx;
    else
    {
    tata[rx]=ry;
    if (h[rx]==h[ry]) h[ry]++;
    }
}

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

void kruskal()
{muchie a;
 int nrsel=0, c1, c2;
while (nrsel<n-1)
      {
       a=H.top(); H.pop();
       c1=Find(a.x); c2=Find(a.y);
       if (c1!=c2)
          {
           sel[nrsel++]=a; costmin+=a.cost;
           Union(c1, c2);
          }
      }
}

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