#include <bits/stdc++.h>

using namespace std;

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

const int nmax=1e5+1;

vector<pair<int, pair<int,int>>> E, sol;

int n, m, T[nmax], cost, x, y, rang[nmax];

long sumcost;

int multime(int nod)
{
  if(T[nod]!=nod) T[nod]=multime(T[nod]);

  return T[nod];
}

void reuneste(int i, int j)
{
  i=multime(i); j=multime(j);

  if(i==j) return;

  if(rang[i]<rang[j]) T[i]=j;

  else T[j]=i;

  if(rang[i]==rang[j]) rang[i]++;

}

void load()
{
  fin>>n>>m;

  for(int i=1;i<=m;++i)
  {
    fin>>x>>y>>cost;

    E.push_back({cost, {x,y}});
  }
}

void kruskal()
{
  sort(E.begin(), E.end());

  for(int i=1;i<=n;++i)
  {
    T[i]=i; rang[i]=1;
  }

  sumcost=0;

  for(auto i: E)
  {
    x=multime(i.second.first);
    y= multime(i.second.second);

    if(x!=y)
    {
      reuneste(x,y); sumcost+=i.first;

      sol.push_back(i);
    }
  }
}

void afis()
{
  fout<<sumcost<<'\n';

  fout<<sol.size()<<'\n';

  for(auto i: sol)
    fout<<i.second.second<<" "<<i.second.first<<'\n';
}

int main()
{
  load();

  kruskal();

  afis();

    return 0;
}