#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

#define MAXN 200003
#define MAXM 400003

#define inFile "apm.in"
#define outFile "apm.out"

struct obj
{
  int x, y, z;
};
struct two
{
  int x, y;
};
using namespace std;

int N, M;

vector<obj> edges;
vector<int> sol;
int cost;
int tata[MAXN];

void read(void)
{
  FILE * f = fopen(inFile, "r");
  fscanf(f, "%d %d", &N, &M);
  for (int i = 1, x, y, z; i <= M; i++)
  {
    fscanf(f, "%d %d %d", &x, &y, &z);
    edges.push_back({x, y, z});
  }
  fclose(f);
}

bool how(obj a, obj b)
{
  return a.z < b.z;
}

void apm(void)
{
  sort(edges.begin(), edges.end(), how);

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

  for (int i = 0; i < M; i++)
  {
    int p1 = edges[i].x;
    int p2 = edges[i].y;

    /* daca extremitatile nu fac parte din aceasi componenta conexa*/
    if (tata[p1] != tata[p2])
    {
      /* unific componentele conexe ale extremitatilor */
      int minim = min(tata[p1], tata[p2]);
      int maxim = max(tata[p1], tata[p2]);

      for (int k = 1; k <= N; k++)
      {
        if (tata[k] == maxim)
        {
          tata[k] = minim;
        }
      }

      /* actualizez solutia */
      sol.push_back(i);
      cost += edges[i].z;
    }
  }
}

void write(void)
{
  FILE * g = fopen(outFile, "w");
  fprintf(g, "%d\n", cost);
  fprintf(g, "%d\n", sol.size());
  for (vector<int>::iterator i = sol.begin(); i != sol.end(); i++)
  {
    fprintf(g, "%d %d\n", edges[*i].x, edges[*i].y);
  }
  fclose(g);
}

int main()
{
  read();
  apm();
  write();

}