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

void Sortare(int s, int d)
{
  graf aux;
  graf piv=G[(s+d)/2];
  int c1,c2;
  c1=s;
  c2=d;
  while(c1<=c2)
  {
    while(G[c1].cost<piv.cost)
      c1++;
    while(G[c2].cost>piv.cost)
      c2--;
    if (c1<=c2)
    {
      aux=G[c1];
      G[c1]=G[c2];
      G[c2]=aux;
      c1++;
      c2--;
    }
  }
  if(s<c2)
    Sortare(s,c2);
  if(c1<d)
    Sortare(c1,d);
}




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;
  Sortare(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;
}