#include "fstream"
#include "algorithm"
#include "vector"

using namespace std;

const int NMax = 200003;

class DSU{
public:
  DSU(int n){
    for(int i = 1; i <= n; ++i){
      father[i] = i;
      rank[i] = 1;
    }
  }
  void Union(int x, int y){
    PrivateUnion(x, y);
  }
  int GetRoot(int x){
    return PrivateGetRoot(x);
  }
  int SameSet(int x, int y){
    if(GetRoot(x) == GetRoot(y)){
      return 1;
    }
    return 0;
  }
private:
  int rank[NMax];
  int father[NMax];
  
  int PrivateGetRoot(int x){
    if(father[x] == x){
      return x;
    }else{
      return father[x] = GetRoot(father[x]);
    }
  }
  void PrivateUnion(int xx, int yy){
    int x = PrivateGetRoot(xx);
    int y = PrivateGetRoot(yy);
    if(rank[x] > rank[y]){
      father[y] = x;
      rank[x] += rank[y];
    }else{
      father[x] = y;
      rank[y] += rank[x];
    }
  }
};


struct Edge{
  int x;
  int y;
  int cost;
};

int n,m;
Edge edge[NMax];

bool cmp(Edge x, Edge y){
  return (x.cost < y.cost);
}
int main(){
  ifstream cin("apm.in");
  ofstream cout("apm.out");

  std::ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  cin >> n >> m;
  for(int i = 1; i <= m; ++i){
    cin >> edge[i].x >> edge[i].y >> edge[i].cost;
  }
  DSU *disjoint_set = new DSU(n);
  vector<pair<int,int> > ans;
  int s = 0;
  sort(edge + 1, edge + 1 + m, cmp);
  for(int i = 1; i <= m; ++i){
    if(!disjoint_set->SameSet(edge[i].x, edge[i].y)){
      s += edge[i].cost;
      ans.push_back(make_pair(edge[i].x, edge[i].y));
      disjoint_set->Union(edge[i].x, edge[i].y);
    }
  }
  cout << s << '\n';
  cout << ans.size() << '\n';
  for(int i = 0; i < (int)ans.size(); ++i){
    cout << ans[i].first << ' ' << ans[i].second << '\n';
  }
}