#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int N;
int M;

struct Edge
{
  int x,y;
  int cost;
};

Edge G[400002];

int m[200002];   /// MULTIME
int sz[200002];  /// UNION FIND TREE SIZE

int cost_total;
vector <pair<int,int> > output;

void Read()
{
  fin>>N>>M;

  for(int i=1; i<=M; ++i)
    fin>>G[i].x>>G[i].y>>G[i].cost;

  fin.close();
}

bool comp(Edge X,Edge Y)
{
  return (X.cost < Y.cost);
}

int Find(int nod)
{
  int root=nod;
  int temp;

  while(root != m[root])
    root=m[root];

  while(nod != m[nod])
    {
      temp=m[nod];
      m[nod]=root;
      nod=temp;
    }

   return root;
}

void Unite(int x,int y)
{
  int root_x=Find(x);
  int root_y=Find(y);

  if(sz[root_x] > sz[root_y])
  {
    m[root_y] = root_x;
    sz[root_x] += sz[root_y];
  }
  else
  {
    m[root_x] = root_y;
    sz[root_y] += sz[root_x];
  }
}

void Do()
{
  for(int i=1; i<=N; ++i)
   m[i]=i,
   sz[i]=1;

  sort(&G[1],&G[M+1],comp);

  int nr_muchii=0;
  int muchie_curenta=0;
  int c1,c2; /// MULTIMILE IN CARE SE AFLA CAPETELE MUCHIEI ALESE

  while(nr_muchii < N-1 && muchie_curenta<=M)
  {
   ++muchie_curenta;

   c1 = Find(G[muchie_curenta].x);
   c2 = Find(G[muchie_curenta].y);

   //fout<<G[muchie_curenta].x<<' '<<G[muchie_curenta].y<<' '<<G[muchie_curenta].cost<<'\n';

   if(c1 != c2)
   {
     Unite(c1,c2);
     ++nr_muchii;
     cost_total+=G[muchie_curenta].cost;
     output.push_back(make_pair(G[muchie_curenta].x,G[muchie_curenta].y));
   }
  }
}

void Print()
{
  fout<<cost_total<<'\n';
  fout<<N-1<<'\n';

  for(int i=0; i<output.size(); ++i)
   fout<<output[i].first<<' '<<output[i].second<<'\n';

  fout.close();
}

int main()
{
    Read();
    Do();
    Print();

    return 0;
}