#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct graf
{
  int v1,v2,cost;
};
vector <graf> G;
int n,m;
vector <int> L;
vector < pair <int,int> > arbore;

void init()
{
  L.resize(n);
  for(int i=0; i<n; i++)
  {
    L[i]=i;
  }
}
int poz(int p,int u)
{ graf piv;
  graf aux;
  int k;
  piv=G[(p+u)/2];
  while (p<u)
  {
    if (G[p].cost>G[u].cost)
    {
      aux=G[p];
      G[p]=G[u];
      G[u]=aux;
    }

    if(G[p].v1==piv.v1&&G[p].v2==piv.v2)
      u--;
    else p++;
  }
  k=p;
  return k;
}

void quicksort(int p,int u)
{int k;
  if (p<u)
  {
    k=poz(p,u);
    quicksort(p,k-1);
    quicksort(k+1,u);
  }
}


int main()
{
  int v_1,v_2,c;
  f>>n>>m;
  for(int i=0; i<m; i++)
  {
    graf cop;
    f>>v_1>>v_2>>c;
    cop.v1=v_1-1;
    cop.v2=v_2-1;
    cop.cost=c;
    G.push_back(cop);
  }

  int i=0,j,k=0,x,y,ct=0;
  quicksort(0,m-1);
  init();
  int numar_muchii=0;
  while(k<n-1)
  {
    if(L[G[i].v1]!=L[G[i].v2])
    {
      k++;
      ct=ct+G[i].cost;
      numar_muchii++;
      arbore.push_back(make_pair((G[i].v1+1),(G[i].v2+1)));
      x=L[G[i].v1];
      y=L[G[i].v2];
      for(j=0; j<n; j++)
        if(L[j]==x)
          L[j]=y;
    }
    i++;
  }
  g<<ct<<"\n"<<numar_muchii<<"\n";

  for(unsigned int i=0; i<arbore.size(); i++)
    g<<arbore[i].first<<" "<<arbore[i].second<<"\n";

  return 0;
}