#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

struct edge {
    int node;
    int cost;
    int parent;

    bool operator < (const edge &a) const {
        return a.cost < cost;
    }
};

class InParser {
    private:
        std::vector<char> str;
        int ptr;
        std::ifstream fin;
    
    private:
        char get_char() {
            if (ptr == (int)str.size()) {
                fin.read(str.data(), (int)str.size());
                ptr = 0;
            }

            return str[ptr++];
        }

        template<class T>
        T get_int() {
            char chr;
            do {
                chr = get_char();
            } while (!isdigit(chr) && (chr != '-'));
            
            int sgn = +1;
            if (chr == '-') {
                sgn = -1;
                chr = get_char();
            }

            T num = 0;
            while (isdigit(chr)) {
                num = num * 10 + (chr - '0');
                chr = get_char();
            }

            return sgn * num;
        }

    public:
        InParser(const char *name) : str((int)1e5), ptr((int)str.size()), fin(name) { }
        ~InParser() { fin.close(); }

        template<class T>
        friend InParser &operator >> (InParser &in, T &num) {
            num = in.get_int<T>();
            return in;
        }
};

class OutParser {
    private:
        std::vector<char> str;
        int ptr;
        std::ofstream fout;
    
    private:
        void put_char(char chr) {
            if (ptr == (int)str.size()) {
                fout.write(str.data(), (int)str.size());
                ptr = 0;
            }

            str[ptr++] = chr;
        }

        template<class T>
        void put_int(T num) {
            if (num < 0) {
                put_char('-');
                num *= -1;
            }

            if (num > 9)
                put_int(num / 10);
            put_char(num % 10 + '0');
        }

    public:
        OutParser(const char *name) : str((int)1e5), ptr(0), fout(name) { }
        ~OutParser() { fout.write(str.data(), ptr); fout.close(); }

        template<class T>
        friend OutParser &operator << (OutParser &out, const T num) {
            out.put_int(num);
            return out;
        }

        friend OutParser &operator << (OutParser &out, const char chr) {
            out.put_char(chr);
            return out;
        }

        friend OutParser &operator << (OutParser &out, const char *str) {
            for (int i = 0; str[i]; i++)
                out.put_char(str[i]);
            return out;
        }
};

const int NMAX = 2e5 + 5;

int n, m, u, v, c;
std::vector<edge> adj[NMAX];
std::vector<std::pair<int, int>> ans;

class MinimumSpanningTree {
    private:
        std::priority_queue<edge> q;
        std::vector<bool> used;
        int n;
    
    public:
        MinimumSpanningTree(const int _n) : n(_n) { }
        ~MinimumSpanningTree() { }

        int prim(int startingNode) {
            used.resize(n + 1, false);
            q.push( { startingNode, 0, 0 } );

            int res = 0;
            while (!q.empty()) {
                edge w = q.top();
                q.pop();

                if (used[w.node])
                    continue;

                used[w.node] = true;
                res += w.cost;
                if (w.parent)
                    ans.push_back( { w.node, w.parent } );

                for (auto neighbour : adj[w.node])
                    if (!used[neighbour.node])
                        q.push( { neighbour.node, neighbour.cost, w.node } );
            }

            return res;
        }
};

int main() {
    InParser cin("apm.in");
    OutParser cout("apm.out");

    cin >> n >> m;
    while (m--) {
        cin >> u >> v >> c;
        adj[u].push_back( { v, c } );
        adj[v].push_back( { u, c } );
    }

    MinimumSpanningTree mst(n);
    cout << mst.prim(1) << '\n';
    cout << ans.size() << '\n';
    for (auto it : ans)
        cout << it.first << ' ' << it.second << '\n';
    return 0;
}