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

using namespace std;

class Multime{
    private:
        int n;
        int *tata, *h;
    public:
        explicit Multime(int);
        ~Multime();

        void initializeaza(int);
        int reprez(int);
        void reuniune(int, int);
};

Multime::Multime(int n) {
    this->n = n;
    tata = new int[n + 1];
    h = new int[n + 1];
}

Multime::~Multime() {
    delete[] tata, h;
}

void Multime::initializeaza(const int u) {
    assert(u >= 1 && u <= n);

    tata[u] = h[u] = 0;
}

int Multime::reprez(int x) {
   while(tata[x])
       x = tata[x];

   return x;
}

void Multime::reuniune(int u, int v) {
    int ru = reprez(u);
    int rv = reprez(v);
    if(h[ru] > h[rv]) {
        tata[rv] = ru;
    }
    else {
        tata[ru] = rv;
        if(h[ru] == h[rv])
            h[rv]++;
    }
}

class Graph {
    private:
        int n, m;
        vector< pair<int, pair<int, int> > > G;
    public:
        ~Graph();

        int getVertex();
        int getEdge();
        pair<int, pair<int, int> > rEdge(int);

        friend istream& operator>>(istream& , Graph&);
};

Graph::~Graph() {
    G.clear();
}

int Graph::getVertex() {
    return this->n;
}

int Graph::getEdge() {
    return this->m;
}

pair<int, pair<int, int> > Graph::rEdge(int pos) {
    assert(pos >= 0 && pos < m);

    return G[pos];
}

istream& operator>>(istream& in, Graph& obj) {
    in >> obj.n >> obj.m;
    int x, y, z;
    for(int i = 0; i < obj.m; ++i) {
        in >> x >> y >> z;
        obj.G.push_back(make_pair(z, make_pair(x, y)));
    }

    sort(obj.G.begin(), obj.G.end());

    return in;
}

class APM{
    private:
        int ct;
        int n, m;
        vector< pair<int, int> > Edge;
    public:
        explicit APM(Graph);
        ~APM();

        friend ostream& operator<<(ostream& ,const APM&);
};

APM::APM(Graph obj) {
    n = obj.getVertex();
    m = n - 1;
    ct = 0;
    Multime r(n);
    for(int i = 1; i <= n; ++i)
        r.initializeaza(i);
    int k = 0;
    for(int i = 0; i < obj.getEdge(); ++i) {
        pair<int, pair<int, int> > muchie = obj.rEdge(i);
        if(r.reprez(muchie.second.first) != r.reprez(muchie.second.second)){
            ct += muchie.first;
            r.reuniune(muchie.second.first, muchie.second.second);
            Edge.push_back(make_pair(muchie.second.first, muchie.second.second));
            ++k;
            if(k == n - 1) {
                break;
            }
        }
    }
    //cout << ct << '\n';
}

APM::~APM() {
    Edge.clear();
}

ostream& operator<<(ostream& out, const APM &obj) {
    out << obj.ct << '\n' << obj.m << '\n';
    for(int i = 0 ; i < obj.Edge.size(); ++i)
        out << obj.Edge[i].first << ' ' << obj.Edge[i].second << '\n';

    return out;
}

int main() {
    ifstream fin("apm.in");
    if(!fin.is_open()) {
        cout << "The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }

    ofstream fout("apm.out");
    if(!fout.is_open()) {
        cout << "The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }

    Graph *A = new Graph();
    fin >> *A;

    APM *K = new APM(*A);

    fout << *K << '\n';

    delete A;
    delete K;

    fin.close();
    fout.close();
    return 0;
}