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

using namespace std;

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

const int N = 1e2 + 5;
vector <muchie> muchii;
int tati[N];
vector <int> raspuns;

bool criteriu(muchie a, muchie b){
return a.cost<b.cost;
}

int main()
{
    int n,m;
    ifstream in("apm.in");
    ofstream out("apm.out");
    in>>n>>m;
    for(int i=1;i<=n;i++){
      tati[i] = i;
    }
    int cost = 0;
    muchie w;
    while(m--){
      in>>w.x>>w.y>>w.cost;
      muchii.push_back(w);
    }
    sort(muchii.begin(),muchii.end(),criteriu);
    for(auto y: muchii){
      if(tati[y.x] != tati[y.y]){
          int val = tati[y.y];
        for(int i=1;i<=n;i++){
          if(tati[i] == val){
            tati[i] = tati[y.x];
          }
        }
      cost += y.cost;
        raspuns.push_back(y.x);
        raspuns.push_back(y.y);
      }
    }
    out<<cost<<'\n';
    int l = raspuns.size();
    out<<l/2<<'\n';
    for(int i=0;i<l;i+=2){
      out<<raspuns[i]<<' '<<raspuns[i+1]<<'\n';
    }

    return 0;
}