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

using namespace std;

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

        const pair<int, pair<int, int> >& operator[](int);
        friend istream& operator>>(istream& , Prim&);
};

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

int Prim::getN() {
    return n;
}

int Prim::getM() {
    return m;
}

const pair<int, pair<int, int> >& Prim::operator[](const int i) {
    assert(i >= 0 && i < m);

    return G[i];
}

istream& operator>>(istream& in, Prim &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)));
    }

    return in;
}

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

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

APM::APM(Prim obj) {
    n = obj.getN();
    m = n - 1;
    int * vis = new int[n + 1];
    int min;
    fill(vis, vis + 1 + n, 0);
    vis[1] = 1;
    pair<int, int> muchie;
    for (int i = 1; i <= n - 1; ++i) {
        min = INT_MAX;
        for (int k = 0; k < obj.getM(); ++k) {
            if (obj[k].first < min
                && vis[obj[k].second.first] != vis[obj[k].second.second]) {
                min = obj[k].first;
                muchie = obj[k].second;
            }
        }
        vis[muchie.first] = vis[muchie.second] = 1;
        ct += min;
        Edge.push_back(muchie);
    }

    delete[] vis;
}

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

ostream& operator<<(ostream &out , const APM &obj) {
    out << obj.ct << '\n' << obj.m << '\n';
    for(int i = 0; i < obj.m; ++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);
    }


    Prim *A = new Prim;
    fin >> *A;

    APM *B = new APM(*A);
    fout << *B << '\n';
    fin.close();
    fout.close();

    delete A;
    delete B;
    return 0;
}