#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
 
using namespace std;

template<typename T>
void printV(const vector<T> &v) {
    for (size_t i = 0; i < v.size(); ++i) {
        cout << v[i] << " ";
    }
    cout << endl;
}

class apm {
private:
    typedef vector<int> VI;
    typedef vector<int>::iterator VIIt;

    typedef pair<int, int> PII;

    struct Comp : public binary_function<bool, PII, PII> {
        bool operator()(const PII &a, const PII &b) const {
            if (a.second < b.second) {
                return true;
            } else if (a.second == b.second) {
                return a.first < b.first;
            }
            return false;
        }
    };

    typedef set<PII, Comp> PQueue;
    typedef PQueue::iterator PQueueIt;

    vector<VI> graf;
    map<PII, int> cost;
    vector<PII> tree;

    int prim(int r) {
        
        static const int INF = ~(1 << 31);

        int total_cost = 0;

        PQueue s;
        s.insert(PII(r, 0));
        for (size_t i = 0; i < graf.size(); ++i) {
            if ((int)i != r) {
                s.insert(PII(i, INF));
            }
        }

        VI scost(graf.size(), INF);
        scost[r] = 0;

        VI ins(graf.size(), 1);
        VI f(graf.size(), -1);

        while (!s.empty()) {

            int u = (s.begin())->first;
            s.erase(s.begin());

            total_cost += scost[u];

       //     cout << u << endl;

            if (f[u] != -1) {
                tree.push_back(PII(f[u], u));
            }
            ins[u] = 0;

            for (size_t i = 0; i < graf[u].size(); ++i) {

                int v = graf[u][i];
                int ecost = cost[PII(u, v)];

                if (ins[v] && scost[v] > ecost) {

                    PQueueIt it = s.find(PII(v, scost[v]));
                    s.erase(it);

                    s.insert(PII(v, ecost));
                    scost[v] = ecost;

                //    cout << v << " - " << ecost << endl;

                    f[v] = u;
                }
            }
        }
        return total_cost;
    }

public:
    void func_apm(ifstream &in, ofstream &out) {
        
        int n, m;
        in >> n >> m;

        vector<VI>(n, VI()).swap(graf);
        cost.clear();

        for (int i = 0; i < m; ++i) {
            int x, y, c;
            in >> x >> y >> c;

            if (x == y) {
                continue;
            }

            graf[x - 1].push_back(y - 1);
            graf[y - 1].push_back(x - 1);

            cost.insert(pair<PII, int>(PII(x - 1, y - 1), c));
            cost.insert(pair<PII, int>(PII(y - 1, x - 1), c));
        }

        /*
        for (size_t i = 0; i < graf.size(); ++i) {
            cout << i << ": ";
            printV<int>(graf[i]);
        }
        for (map<PII, int>::iterator i = cost.begin(); i != cost.end(); ++i) {
            cout << "(" << i->first.first << ", " << i->first.second << ") = "
                << i->second << endl;
        }
        */

        out << prim(0) << endl;
        out << tree.size() << endl;

        for (size_t i = 0; i < tree.size(); ++i) {
            out << tree[i].first + 1 << " " << tree[i].second + 1 << endl;
        }
    }
};

int main() {
    ifstream in("apm.in");
    ofstream out("apm.out");

    apm x; x.func_apm(in, out);
}