#include <bits/stdc++.h>

using namespace std;

typedef tuple<int, int, int>muchie;
int main() {
  ifstream cin("apm.in");
  ofstream cout("apm.out");

  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>>g(n);
  for(int i = 0; i < m; ++i) {
    int x, y, c;
    cin >> x >> y >> c;
    x--, y--;

    g[x].emplace_back(y, c);
    g[y].emplace_back(x, c);
  }
  auto cmpCost = [&] (const muchie & a, const muchie & b) {
    if(get<2>(a) == get<2>(b))
      return make_pair(get<0>(a), get<1>(a)) < make_pair(get<0>(b), get<1>(b));
    return get<2>(a) < get<2>(b);
  };
  multiset<tuple<int, int, int>, decltype(cmpCost)>S(cmpCost);
  long long mst_cost = 0;
  vector<bool>picked(n);
  auto add_to_mst = [&] (int u) {
    for(auto it : g[u]) {
      muchie now(min(u, it.first), max(u, it.first), it.second);
      if(picked[it.first]) {
        S.erase(S.find(now));
      } else S.insert(now);
    }
    picked[u] = true;
  };
  add_to_mst(0);
  vector<pair<int, int>>mst_edges;
  for(int i = 0; i < n - 1 && !S.empty(); ++i) {
    muchie aleg = *S.begin();
    mst_edges.emplace_back(get<0>(aleg), get<1>(aleg));
    mst_cost += get<2>(aleg);

    if(!picked[get<0>(aleg)])
      add_to_mst(get<0>(aleg));
    else add_to_mst(get<1>(aleg));
  }
  cout << mst_cost << '\n' << n - 1 << '\n';
  for(pair<int, int>p : mst_edges)
    cout << p.first + 1 << ' ' << p.second + 1 << '\n';
}