#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;
}

int search(int nod)
{
  if (tata[nod] != nod)
    tata[nod] = search(tata[nod]);
  return tata[nod];
}

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 = search(edges[i].x);
    int p2 = search(edges[i].y);

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

      /* 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();

}