#define fisier "apm"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
#define range(i, n) for (int i = 0; i < n; i++)



const int
N = 200000,
M = 2*N,
C = 1000;

struct Arc {int b, cost;};
struct Muchie {int a, b, cost;};
inline bool operator < (Arc& a, Arc& b) {return a.cost < b.cost;}
inline bool operator < (Muchie& a, Muchie& b) {return a.cost < b.cost;}
inline std::istream& operator >> (std::istream& in, Muchie& m) {in >> m.a >> m.b >> m.cost; m.a--, m.b--; return in;}
inline std::ostream& operator << (std::ostream& out, Muchie& m) {return out << m.a+1 << ' ' << m.b+1 << '\n';}

#include <vector>
namespace dj
{
    int set[N];

    void reset(int n)
    {range(i, n) set[i] = -1;}

    int rad(int x)
    {
        std::vector<int> drum;
        while (set[x] >= 0)
        {
            drum.push_back(x);
            x = set[x];
        }
        for (auto y: drum)
            set[y] = x;
        return x;
    }

    void uneste(int ra, int rb)
    {
        if (set[ra] > set[rb])
            std::swap(ra, rb);
        set[ra] += set[rb];
        set[rb] = ra;
    }
}

template class std::vector<int>; // Pentru depanare
template class std::vector<Muchie>;
template <typename Type> // Type are operatorul <
struct heap
{
    std::vector<Type> vector;

    inline Type top() // O(1)
    {return vector.front();}

    inline int _fiu0(int idx1) {return idx1 << 1;} // idx1 - Index de la 1.
    inline int _fiu1(int idx1) {return (idx1 << 1)+1;}
    inline int _tata(int idx1) {return idx1 >> 1;}

    inline int fiu0(int idx) {return _fiu0(idx+1)-1;} // idx - Index de la 0.
    inline int fiu1(int idx) {return _fiu1(idx+1)-1;}
    inline int tata(int idx) {return idx? _tata(idx+1)-1: 0;}

    void sink()
    {
        int i = 0, fiu;
        while (fiu0(i) < vector.size())
        {
            if (fiu1(i) >= vector.size() || vector[fiu0(i)] < vector[fiu1(i)])
                fiu = fiu0(i); /// !!! Iau fiul minim. (greseala periculoasa) (#1)
            else               //       ^ Greseala de a nu face asta m-a dus la o ora si jumatate de depanare constanta
                fiu = fiu1(i);
            if (vector[fiu] < vector[i])
            {
                std::swap(vector[fiu], vector[i]);
                i = fiu;
            }
            else
                break; // Nu este chiar codas. Ne oprim aici. (#2)
        }

    }

    void rise()
    {
        int i = (int)vector.size() - 1;
        while (vector[i] < vector[tata(i)])
        {
            std::swap(vector[i], vector[tata(i)]);
            i = tata(i);
        }
    }

    void pop() // O(log vector.size())
    {
        std::swap(vector.front(), vector.back());
        vector.pop_back();
        sink();
    }

    void push(Type val) // O(log vector.size())
    {
        vector.push_back(val);
        rise();
    }
};

namespace apm // A se face dj::reset() inainte de apm::prim(...)
{
    Arc tata[N];
    int rank[N], cost;
    std::vector<Muchie> muchii;

    void prim(std::vector<Arc>* vecini, int radacina)
    {
        heap<Muchie> inventar;
        auto adauga_vecini = [&inventar, vecini](int a)
        {
            for (auto arc: vecini[a])
                if (arc.b != a) // Optimizare minora: Nu te intoarce in arbore
                    inventar.push({a, arc.b, arc.cost});
        };
        adauga_vecini(radacina);
        while (inventar.vector.size())
        {
            Muchie muchie = inventar.top();
            inventar.pop();
            int ra = dj::rad(radacina), rb = dj::rad(muchie.b);
            if (ra != rb) // ^^^^^^^^ \\ !!! (Avem o singura componenta in arborele care se formeaza; putem folosi radacina)
            {
                dj::uneste(ra, rb); ///
                muchii.push_back(muchie);
                cost += muchie.cost;
                tata[muchie.b] = {muchie.a, muchie.cost};
                rank[muchie.b] = rank[muchie.a] + 1;
                adauga_vecini(muchie.b); ///
            }
        }
    }
}



std::vector<Arc> vecini[N];
int main()
{

    int n, m;
    in >> n >> m;
    while (m--)
    {
        Muchie m; // Nu va interfera cu celalalt m.
        in >> m; //  Muchia este stearsa inainte de verificarea conditiei
        vecini[m.a].push_back({m.b, m.cost});
        vecini[m.b].push_back({m.a, m.cost});
    }
    dj::reset(n);
    apm::prim(vecini, 0);
    out << apm::cost << '\n' << n - 1 << '\n';
    for (Muchie muchie: apm::muchii)
        out << muchie;
}