#include <iostream>
#include <vector>
#include <cassert>
#include <fstream>
#include <climits>
#include <algorithm>
#include <queue>
#define INF (2e9)
using namespace std;

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

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

Prim::~Prim() {
    /*for(int i = 0; i <= n; ++i)
        G[i].clear();
    delete[] G;
     */
}

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

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

const vector< pair<int, int> >& Prim::operator[](const int i) {
    assert(i >= 1 && i <= n);

    return G[i];
}

istream& operator>>(istream& in, Prim &obj) {
    in >> obj.n >> obj.m;
    obj.G = new vector< pair<int, int> >[obj.n + 1];
    int x, y, z;
    for(int i = 0; i < obj.m; ++i) {
        in >> x >> y >> z;
        obj.G[x].push_back(make_pair(y, z));
        obj.G[y].push_back(make_pair(x, z));
    }

    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;
    ct = 0;
    int * d = new int[n + 1];
    int * tata = new int[n + 1];
    int * vis = new int[n + 1];
    fill(tata, tata + 1 + n, 0);
    fill(vis, vis + 1 + n, 1);
    priority_queue<pair<int, int>, vector< pair<int, int> > , greater<pair<int, int> > > H;
    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
    }
    d[1] = 0;

    //H.push(make_pair(0, 1));
    int s = 1;
    vis[s] = 1;
    H.push(make_pair(0, 1));
    while (!H.empty()) {
        int u = H.top().second;
        //cout << H.top().first << ' '<< H.top().second << '\n';
        H.pop();
        for (int i = 0; i < obj[u].size(); ++i) {
            int v = obj[u][i].first;
            if (vis[v] == 1 && obj[u][i].second < d[v]) {
                d[v] = obj[u][i].second;
                H.push(make_pair(d[v], v));
                //cout << H.top().first <<' ' << H.top().second << '\n';
                tata[v] = u;
            }
        }
        //cout << "\n\n";
        if(u != s && vis[u] == 1) {
            vis[u] = 0;
            ct += d[u];
            Edge.push_back(make_pair(tata[u], u));
        }
    }
    /* for(auto it = H.begin(); it != H.end(); ++it)
        cout << it->first <<' ' << it->second << '\n';
*/
    delete[] d;
    delete[] tata;
    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;
}