/// Kruskal - O(m log n) - UNION si FIND (structuri de multimi disjuncte)

/// - sortarea muchiilor m log m
/// - memorarea componentelor conexe ca arbori, folosind vectorul tata
/// - reprezentantul componentei va fi radacina arborelui

/// - reuniunea a 2 arbori
///       - radacina unui arbore devine fiu al radacinii celuilalt arbore
///       - arborele cu inaltime mai mica devine subarbore al radacinii celuilalt arbore
///         (reuniune ponderata) pentru a obtine arbori cu inaltime cat mai mica
///


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

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

const int Nmax=200000;
const int Mmax=400000;

int n; /// numarul de noduri
int m; /// numarul de muchii

struct muchie
{ int x,y,cost;};

vector <muchie> G;  /// vectorul de muchii

int tata[Nmax]; /// memorarea componentelor conexe, folosind vectorul tata
int h[Nmax];    /// inaltimea fiecarui arbore

vector <int> Solutie; /// memoreaza indicii muchiilor selectate

void Citire()
{ muchie E;
  fin>>n>>m;
  for(int i=0; i<m; i++)
    { fin>>E.x>>E.y>>E.cost;
      G.push_back(E);
    }
}

/// initial se pleaca de la n componente conexe, formate fiecare dintr-un nod
void Initializare()
{ for(int i=1; i<=n; i++)
     tata[i]=h[i]=0;
}

/// returneaza radacina arborelui care contine nodul u
int Reprez(int u)
{ while(tata[u]!=0) u=tata[u];
  return u;
}

/* Compresia caii
int Reprez(int u)
{ if(tata[u]==0) return u;
  tata[u]=Reprez(tata[u]);
  return tata[u];
}
*/

/// reuniurea arborilor din care fac parte nodurile u si v
void Reuneste(int u, int v)
{ int ru=Reprez(u);
  int rv=Reprez(v);
  if(h[ru]>h[rv]) tata[rv]=ru;
  else  if(h[rv]>h[rv]) tata[ru]=rv;
        else {tata[ru]=rv; h[rv]++; }
}

int Kruskal()
{  int costAPM=0;
   Initializare();
   for(int i=0, sel=0; sel<n-1 && i<m; i++) /// cat timp nu au fost selectate n-1 muchii
       if(Reprez(G[i].x)!=Reprez(G[i].y)) /// verificam dca muchia i are cele 2 extremitati in componente conexe diferite
          {  sel++;  /// selectam muchia
             costAPM+=G[i].cost; /// actualizam costul arborelui de cost minim
             Solutie.push_back(i);
             Reuneste(G[i].x,G[i].y); /// reunim comp. conexe. coresp. nodurilor x si y

          }
   return costAPM;
}

void Afisare_Graf()
{ for(auto e: G)
      fout<<e.x<<" "<<e.y<<" "<<e.cost<<"\n";

}

void Afisare_Solutie()
{ for(auto e: Solutie)
      fout<<G[e].x<<" "<<G[e].y<<"\n";

}

bool operator<(muchie m1, muchie m2)
{ return m1.cost<m2.cost;
}

int main()
{   Citire();
    sort(G.begin(),G.end());
    ///Afisare_Graf();
    fout<<Kruskal()<<"\n";
    fout<<Solutie.size()<<"\n";
    Afisare_Solutie();
    return 0;
}