#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define d double
#define in int
#define si(x) scanf('%d', &x)
#define sl(x) scanf('%lld', &x)
#define ss(s) scanf('%s', s) 
#define pi(x) printf('%d', x)
#define pl(x) printf('%lld', x)
#define ps(s) printf('%s', s) 
#define pb push_back 
#define mp make_pair 
#define F first 
#define S second 
#define all(x) x.begin(), x.end() 
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x)) 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pl; 
typedef vector<int> vi; 
typedef vector<ll> vl; 
#define modulo 1000000007
#define FOR(i,a,b) for(int i=a;i<=b;i++)
typedef vector<pii> vpii;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{
  int x,y,cost;
};

int n,m;
int x,y,c;
vector<muchie> graf;
vector<muchie>rezultat;
vector<int> vizitat;
int costTotal;

bool comparator(const muchie &a, const muchie &b){
  return a.cost < b.cost;
}

vector<int> tata, h;

void Initializare(int u){
  tata[u] = h[u] = 0;
}

int Reprezentant(int u){
  while(tata[u] != 0)
    u = tata[u];
  return u;
}

void Reuneste(int u, int v){
  int r1 = Reprezentant(u);
  int r2 = Reprezentant(v);
  if(h[r1] > h[r2]){
    tata[r2] = r1;
  }
  else{
    tata[r1] = r2;
    if(h[r1] == h[r2]){
      h[r2] = h[r1] + 1;
    }
  }
}

void afisare(){
  fout<<costTotal<<endl;
  fout<<rezultat.size()<<endl;
  for(int i=0;i<rezultat.size();i++){
    fout<<rezultat[i].x<<" "<<rezultat[i].y<<endl;
  }
}

void Kruskal(){
  // sortare graf dupa cost
  sort(graf.begin(), graf.end(), comparator);
  tata = h = vector<int>(n+1, 0);
  for(int i=1;i<=n;i++)
    Initializare(i);
  
  int nrMuchii = 0;
  for(int i=0;i<graf.size();i++){
    int x = graf[i].x;
    int y = graf[i].y;
    if(Reprezentant(x) != Reprezentant(y)){
      rezultat.push_back({x,y, graf[i].cost});
      Reuneste(x,y);
      nrMuchii += 1;
      costTotal += graf[i].cost;
      if(nrMuchii == n-1)
        break;
    }
  }
  afisare();
}

void read(){
  fin>>n>>m;
  graf = vector<muchie>();
  for(int i=0;i<m;i++){
    fin>>x>>y>>c;
    muchie aux = {x,y,c};
    graf.push_back(aux);
  }
  Kruskal();
}

int main() 
{
  ios_base::sync_with_stdio(0), fin.tie(0), fout.tie(0);
  read();

  return 0;
}