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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct Muchie{
    int x,y,c;
    Muchie(int _x=0, int _y=0, int _c=0)
        : x(_x), y(_y), c(_c) {}
};

int n,m,x,y,c;
vector<Muchie> muchii;
vector<Muchie> muchiiAPM;
int costTotal = 0;
vector<int> tata;
vector<int> rang;

int getTata(int nod){
    if(tata[nod] != nod){
        tata[nod] = getTata(tata[nod]);
    }
    return tata[nod];
}

void unire(int x, int y){
    if(rang[x] < rang[y]){
        tata[x] = y;
    }
    else if(rang[x] > rang[y]){
        tata[y] = x;
    }
    else{
        tata[x] = y;
        rang[y]++;
    }
}

void kruskal(){
    for(auto& edge: muchii){
        int tataX = getTata(edge.x);
        int tataY = getTata(edge.y);

        if(tataX != tataY){
            unire(tataX, tataY);
            muchiiAPM.push_back(Muchie(edge.x,edge.y,0));

            costTotal += edge.c;
        }
    }
}

int main(){
    f >> n >> m;
    rang.resize(n+1, 0);
    tata.resize(n+1);
    for(int i=1; i<=n; i++)
        tata[i] = i;
    for(int i=1; i<=m; i++){
        f >> x >> y >> c;
        muchii.push_back(Muchie(x,y,c));
    }
    sort(muchii.begin(), muchii.end(), [](const Muchie& a, const Muchie& b){
        return a.c < b.c;
    });
    kruskal();
    g << costTotal << '\n';
    g << n-1 << '\n';
    for(auto& e: muchiiAPM){
        g << e.x << " " << e.y << '\n';
    }

    return 0;
}