#include <bits/stdc++.h>
#define NMAX 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<int,pair<int,int>>>g;
int link[NMAX], lg[NMAX];
int find (int x) {
  while (x != link[x]) x = link[x];
  return x;
}
bool same (int a, int b)
{
  return find(a) == find(b);
}
void unite (int a, int b) 
{
  a = find(a);
  b = find(b);
  if (lg[a] < lg[b]) swap (a, b);
  lg[a] += lg[b];
  link[b] = a;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i){
    int x, y, w;
    cin >> x >> y >> w;
    g.push_back({w, {x, y}});
  }
  sort (g.begin(), g.end());
  for (int i = 1; i <= n; ++i)
  {
    link[i] = i;
    lg[i] = 1;
  }
  int cnt = 0;
  vector<pair<int,int>>ans;
  for (auto p: g) {
    int a = p.second.first, b = p.second.second;
    if (!same(a,b)){
      cnt += p.first;
      ans.push_back({a, b});
      unite(a,b); 
    }
  }
  cout << cnt << '\n' << ans.size() << '\n';
  for (auto p: ans)
    cout << p.first << ' ' << p.second << '\n';
}