#include <fstream>
#include <algorithm>
using namespace std;

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

struct Muchie
{
  int x,y,c;
};

int G[200005],R[200005],Idx[400005];
int N,M,k,Sol;
Muchie E[400005];

bool Compare(Muchie A, Muchie B)
{
  return A.c < B.c;
}

void Read()
{
  fin >> N >> M;
  for(int i = 1; i <= M; ++i)
  {
    fin >> E[i].x >> E[i].y >> E[i].c;
  }
  sort(E + 1, E + M + 1,Compare);
}

int Root(int X)
{
  while(X != G[X])
    X = G[X];
  return X;
}

void Unite(int X, int Y)
{
  if(R[X] < R[Y])
     G[X] = Y;
  if(R[X] > R[Y])
     G[Y] = X;
  if(R[X] == R[Y])
  {
      G[Y] = X;
      R[X]++;
  }
}

void Solve()
{

  for(int i = 1; i <= N; ++i)
    G[i] = i;

  for(int i = 1; i <= M; ++i)
    {
      int R1 = Root(E[i].x);
      int R2 = Root(E[i].y);
      if(R1 != R2)
      {
        Unite(R1,R2);
        Sol += E[i].c;
        Idx[++k] = i;
      }
    }
}

void Print()
{
  fout << Sol << "\n" << N - 1 << "\n";
  for(int i = 1; i <= k; ++i)
   fout << E[Idx[i]].x << " " << E[Idx[i]].y << "\n";
}

int main()
{
    Read();
    Solve();
    Print();
}