#include <fstream>
#include <vector>
#include <algorithm>
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
const int NMAX=200005;

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

struct edge
{
  int a, b, c;

  bool operator< (const edge& other) const
  {
    if(c==other.c)
    {
      if(a==other.a) return b<other.b;
      return a<other.a;
    }
    return c<other.c;
  }
};

int find(int);
bool un(int, int);
void kruskal();

vector <edge> muchii;
vector <pair <int, int>> vans;
int t[NMAX];
int n, m;

int main()
{
  ios_base::sync_with_stdio(false);
  fin.tie(0);
  fout.tie(0);
  int i, a, b, c;
  fin>>n>>m;
  for(i=1; i<=n; i++) t[i]=i;
  for(i=1; i<=m; i++)
  {
    fin>>a>>b>>c;
    muchii.push_back({a, b, c});
  }
  sort(muchii.begin(), muchii.end());
  kruskal();
}

void kruskal()
{
  int cnt=0, i=0;
  int nod1, nod2;
  long long ans=0;
  while(cnt<n && i<m)
  {
    nod1=muchii[i].a;
    nod2=muchii[i].b;
    if(un(nod1, nod2))
    {
      cnt++;
      ans+=muchii[i].c;
      vans.push_back(make_pair(nod1, nod2));
    }
    i++;
  }
  fout<<ans<<'\n';
  fout<<n-1<<'\n';
  for(auto j:vans) fout<<j.first<<' '<<j.second<<'\n';
}

bool un(int a, int b)
{
  int ta=find(a);
  int tb=find(b);
  if(ta<tb)
  {
    t[tb]=ta;
    return true;
  }
  else if(ta>tb)
  {
    t[ta]=tb;
    return true;
  }
  return false;
}

int find(int nod)
{
  if(t[nod]==nod) return nod;
  t[nod]=find(t[nod]);
  return t[nod];
}