#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
ifstream in ("apm.in");
ofstream out ("apm.out");
int const nmax = 200000;

struct muchie{
  int x;
  int y;
  int cost;
  bool operator < (muchie a) const{
    return cost < a.cost;
  }

};
int n ,m;
muchie v[5 + nmax * 2];
vector <vector<int>> mult;
int arbore[5 + nmax];
int s = 0;
vector <muchie> sol;
void reunion(int gala,int galb){
  if(gala != galb){
    if(mult[gala].size() < mult[galb].size()){
      for(int i = 0 ; i < mult[gala].size() ;i++){
        mult[galb].push_back(mult[gala][i]);
        arbore[mult[gala][i]] = galb;
      }
      mult[gala].clear();
    } else{
      for(int i = 0 ; i < mult[galb].size() ;i++){
        mult[gala].push_back(mult[galb][i]);
        arbore[mult[galb][i]] = gala;
      }
      mult[galb].clear();
    }
  }
}
int main()
{
  in>>n>>m;

  for(int i = 0; i <= n ;i++){
    arbore[i] = i;
    vector<int> temp ;
    temp.push_back(i);
    mult.push_back(temp);
  }
  for(int i = 0 ; i < m ;i++){
    in>>v[i].x>>v[i].y>>v[i].cost;
  }
  sort(v,v + m);
  for(int i = 0 ; i < m ;i++){

    if(arbore[v[i].x] != arbore[v[i].y]){
      s += v[i].cost;
      sol.push_back(v[i]);
      reunion(arbore[v[i].x] , arbore[v[i].y]);
    }
  }
  out<<s<<'\n';
  out<<sol.size()<<'\n';
  for(int i = 0 ; i < sol.size() ;i++){
    out<<sol[i].x<<" "<<sol[i].y<<" "<<'\n';
  }
  return 0;
}