#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

using edge = pair <pair <int, int>, int>;
using pii = pair <int, int>;

int n, m;
vector <edge> v, ans;
vector <pii> dsu;
vector <pii> G;

bool cmp(const edge &a, const edge &b){
  return a.second < b.second;
}

int getRoot(int x){
  if (dsu[x].first == x)
    return x;
  dsu[x].first = getRoot(dsu[x].first);
  return dsu[x].first;
}

bool join(int x, int y){
  x = getRoot(x);
  y = getRoot(y);
  if (x == y)
    return false;
  if (dsu[x].second < dsu[y].second)
    swap(x, y);
  dsu[y].first = x;
  dsu[x].second += dsu[y].second;
  return true;
}

void init(){
  fin >> n >> m;
  v.resize(m);
  for (int i = 0; i < m; i++)
    fin >> v[i].first.first >> v[i].first.second >> v[i].second;
  sort(v.begin(), v.end(), cmp);
  dsu.resize(n + 1);
  for (int i = 1; i <= n; i++)
    dsu[i] = {i, 1};
}

void solve(){
  for (int i = 0; i < m; i++)
    if (join(v[i].first.first, v[i].first.second))
      ans.push_back(v[i]);
}

void answer(){
  int s = 0;
  for (int i = 0; i < n - 1; i++)
    s += ans[i].second;
  fout << s << "\n" << n - 1 << "\n";
  for (int i = 0; i < n - 1; i++)
    fout << ans[i].first.first << " " << ans[i].first.second << "\n";
}

int main(){
  init();
  solve();
  answer();
  return 0;
}