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

std::ifstream fin("grafpond.in");
std::ofstream fout("grafpond.out");

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

bool cmp(edge x, edge y) { return (x.cost < y. cost); }

std::vector<edge> muchie;
std::vector<edge> apm;

int tata[101], rang[101];

int Find(int x){

        int root, y;

        for(root = x; root != tata[root]; root = tata[root]);

                //path compresion
                while(tata[x] != x) {
                        y = tata[x];
                        tata[x] = root;
                        x = y;
                }

        return root;
}

void Union(int x, int y){

        if(Find(x)!=Find(y)) {
                if(rang[x] > rang[y]) {
                        tata[y] = x;
                }
                else if(rang[x] < rang[y]) {
                        tata[x] = y;
                }
                else{
                        tata[y] = x;
                        rang[x]++;
                }
        }
}
int main(){

  int n, m;
  fin>>n>>m;
  for(int i = 1 ; i <= n ; i++){
    tata[i] = i;
    rang[i] = 1;
  }
  for(int i = 1 ; i <=m ;i++){
    int x, y, c;
    edge e;
    fin>>x>>y>>c;
    e.x = x;
    e.y = y;
    e.cost = c;
    muchie.push_back(e);
  }

  sort(muchie.begin(), muchie.end(), cmp);

  for( auto j : muchie){
    if(Find(j.x) != Find(j.y)){
      apm.push_back(j);
      Union(Find(j.x), Find(j.y));
    }
  }
  int sum = 0;
  for(auto j : apm){
    sum += j.cost;
  }

  fout<<sum<<"\n"<<apm.size()<<"\n";
  for(auto j : apm){
    fout<<j.x<<" "<<j.y<<"\n";
  }
  return 0;
}