#define fisier "A"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");

#define range(i, n) for (int i = 0; i < n; i++)
#define iter(i, v) for (auto i: v)



const int
N = 100000,
M = 4*N;

struct Arc {int b, cost;};
struct Muchie {int a, b, cost;};
std::ostream& operator << (std::ostream& stream, Muchie& muchie)
{return stream << muchie.a << ' ' << muchie.b << '\n';}

int n;

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

    void reset() // O(n) // A se apela inainte de utilizare, ca de nu esti mort.
    {range (i, n) set[i] = -1;}

    int rad(int x) // O(log n) sau O(1).
    {
        std::vector<int> drum;
        while (set[x] >= 0)
        {
            drum.push_back(x);
            x = set[x];
        }
        iter (y, drum) // Compresie de drum pentru O(1).
            set[y] = x;
        return x;
    }

    void uneste(int rad_a, int rad_b) // O(1)
    {
        if (set[rad_a] > set[rad_b]) // Daca a are mai putine.
            std::swap(rad_a, rad_b);
        set[rad_a] += set[rad_b];
        set[rad_b] = rad_a;
    }
}

#include <queue>
namespace apm
{
    Arc tata[N]; // "tata[i].b = -1" <=> "i este radacina""
    int rank[N], suma;
    std::vector<Muchie> muchii;

    struct CompMuchie // Vrem cost minim
    {inline bool operator () (Muchie& a, Muchie& b) {return a.cost > b.cost;}};

    void reset()
    {range(i, n) {tata[i].b = -1; rank[i] = 0;}}

    void eval(std::vector<Arc>* vecini, int radacina)
    {
        std::priority_queue // Heap
        <Muchie, std::vector<Muchie>, CompMuchie> inventar;

        auto push_vecini = [vecini, &inventar](Muchie muchie)
        {iter (arc, vecini[muchie.b]) if (arc.b != muchie.a) inventar.push({muchie.b, arc.b, arc.cost});};

        push_vecini({-1, radacina, -1});

        // disjunct::reset(); // Nu este necesar pentru fiecare APM, ci doar la inceput
        while (!inventar.empty())
        {
            Muchie muchie = inventar.top();
            inventar.pop();

            int
            rad_a = disjunct::rad(muchie.a),
            rad_b = disjunct::rad(muchie.b);

            if (rad_a != rad_b)
            {
                disjunct::uneste(rad_a, rad_b);
                push_vecini(muchie);
                muchii.push_back(muchie);
                suma += muchie.cost;
                tata[muchie.b] = {muchie.a, muchie.cost};
                rank[muchie.b] = rank[muchie.a] + 1;
            }
        }
    }
}




std::vector<Arc> vecini[N];

int main()
{
    int m;
    in >> n >> m;

    while (m--)
    {
        int a, b, cost;
        in >> a >> b >> cost;
        a--, b--;
        vecini[a].push_back({b, cost});
        vecini[b].push_back({a, cost});
    }

    disjunct::reset();
    apm::reset();

    apm::eval(vecini, 0); // 0, nod arbitrar

    out << apm::suma << '\n' << n - 1 << '\n';
    iter (muchie, apm::muchii)
        out << muchie;
}