#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
#define Nmax 200005
#define InFile "apm.in"
#define OutFile "apm.out"
#define pb push_back

using namespace std;

int n, m, q, L, Cost;
int h[Nmax], ft[Nmax];
struct Muchie {int x, y, c;} H[Nmax];
struct Ceva {int x, y;} Rasp[Nmax];
vector <int> A[Nmax], C[Nmax];

void read();
void APM();
void ins_nod(int);
void ins_mc(Muchie);
inline int fth (int x) {return x/2;}
inline int lson (int x) {return 2*x;}
inline int rson (int x) {return 2*x+1;}
void up_heap (int k);
void down_heap(int k);
void extract_max();
int find (int);
void Unite(int, int);
void write();

int main()
{
  assert (freopen (InFile, "r", stdin));
  assert (freopen (OutFile, "w", stdout));
  read();
  APM();
  write();
  return 0;
}

void read()
{
  int i, x, y, c;
  scanf ("%d %d\n", &n, &m);
  for (i=1; i<=m; i++)
  {
    scanf ("%d %d %d\n", &x, &y, &c);
    A[x].pb(y); C[x].pb (c);
    A[y].pb(x); C[y].pb (c);
  }
}

void APM ()
{
  int i, gas;
  Muchie mc;
  for (i=1; i<=n; i++) ft[i]=i;
  ins_nod (1);
  for (i=2; i<=n; i++)
  {
    do
    {
      gas=1;
      mc=H[1]; extract_max();
      if (find (mc.x)==find (mc.y))
        gas=0;
    }
    while (!gas);
    Cost+=mc.c; Rasp[++q].x=mc.x; Rasp[q].y=mc.y;
    Unite (mc.x, mc.y);
    ins_nod (mc.y);
  }
}

void ins_nod (int nd)
{
  int i, lg=A[nd].size();
  Muchie z;
  for (i=0; i<lg; i++)
  {
    z.x=nd; z.y=A[nd][i]; z.c=C[nd][i];
    if (find (z.x) != find (z.y))
      ins_mc (z);
  }
}

void ins_mc (Muchie A)
{
  H[++L]=A;
  up_heap (L);
}

void up_heap (int k)
{
  Muchie key=H[k];
  while (k>1 && key.c<H[fth(k)].c)
    H[k]=H[fth(k)], k=fth(k);
  H[k]=key;
}

void extract_max()
{
  swap (H[1], H[L--]);
  down_heap (1);
}

void down_heap(int k)
{
  int son;
  do
  {
    son=0;
    if (lson(k)<=L)
    {
      son=lson(k);
      if (rson (k)<=L && H[lson(k)].c>H[rson(k)].c)
        son=rson (k);
      if (H[son].c > H[k].c)
        son=0;
    }
    if (son)
    {
      swap (H[k], H[son]);
      k=son;
    }
  }
  while (son);
}

int find (int x)
{
  int val=x, ax;
  while (ft[val]!=val)
    val=ft[val];
  while (ft[x]!=x)
  {
    ax=ft[x];
    ft[x]=val;
    x=ax;
  }
  return val;
}

void Unite (int x, int y)
{
  int c1=find (x), c2=find (y);
  if (c1!=c2)
  {
    if (h[c1]>h[c2]){
      ft[y]=x; return;}
    if (h[c1]<h[c2]){
      ft[x]=y; return;}
    ft[y]=x; h[x]++;
  }
}

void write()
{
  int i;
  printf ("%d\n", Cost);
  printf ("%d\n", q);
  for (i=1; i<=q; i++)
    printf ("%d %d\n", Rasp[i].x, Rasp[i].y);
}