#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=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[c1];
G[c1]=aux;
c1++;
c2--;}}
        if(c1<d)
        Sortare(c1,d);
        if(s<c2)
        Sortare(s,c2);
}
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;
}