#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n, m, r[200005], t[200005], x, y, z, cost;

struct muchie
{
  int a, b, cost;
};

vector<muchie> v;
vector<pair<int, int>> rez;

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

void Read()
{
  f>>n>>m;
  for(int i = 1;i <= m;++i)
    f>>x>>y>>z, v.push_back({x, y, z});
  sort(v.begin(), v.end(), cmp);
}

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

void unite(int x, int y)
{
  if(r[x] > r[y])
    t[y] = x, r[x] += r[y];
  else
    t[x] = y, r[y] += r[x];
}

void Solve()
{
  for(int i = 1;i <= n;++i)
    r[i] = 1, t[i] = i;
  for(auto it : v)
    if(find(it.a) != find(it.b))
      cost += it.cost, unite(find(it.a), find(it.b)), rez.push_back(make_pair(it.a, it.b));
  g<<cost<<'\n';
  g<<rez.size()<<'\n';
  for(auto it : rez)
    g<<it.first<<" "<<it.second<<'\n';
}

int main()
{
  Read();
  Solve();
  return 0;
}