#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin ("apm.in");
ofstream cout("apm.out");
int n, m, a, b, c, parent[200005], h[200005], ans;

struct elem{
  int a, b, c;
};

vector <elem> edge;
vector < pair <int, int> > ans_edge;

bool comp(elem x, elem y){
  return x.c < y.c;
}

int Find(int x)
{
  if(parent[x] == x)
    return x;
  else
    return Find(parent[x]);
}

void Union(int x, int y)
{
  int x_parent = Find(x);
  int y_parent = Find(y);

  if(x_parent != y_parent)
  {
    if(h[x_parent] < h[y_parent]){
      parent[x_parent] = y_parent;
    }
    else if(h[y_parent] < h[x_parent]){
      parent[y_parent] = x_parent;
    }
    else if(h[x_parent] == h[y_parent]){
      parent[x_parent] = y_parent;
      h[y_parent]++;
    }
  }
}
int main()
{
  cin >> n >> m;
  for(int i = 1; i <= m; i++){
    cin >> a >> b >> c;
    edge.push_back({a, b, c});
  }
  for(int i = 1; i <= n; i++)
    parent[i] = i;

  sort(edge.begin(), edge.end(), comp);

  for(int i = 0; i < edge.size(); i++)
  {
    int x = edge[i].a, y = edge[i].b;
    int cost = edge[i].c;
    if(Find(x) != Find(y))
    {
      Union(x, y);
      ans += cost;
      ans_edge.push_back({x, y});
    }
  }

  cout << ans <<'\n';
  cout << ans_edge.size() <<'\n';
  for(auto e : ans_edge)
    cout << e.first <<' '<< e.second << '\n';

  return 0;
}