#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <memory>

using namespace std;

class Writer {
  public:
    Writer(ostream& stream):
        m_stream(stream),
        m_buffer(new char[kBufferSize]) {
        memset(m_buffer.get(), 0, sizeof(char) * kBufferSize);
        m_pos = 0;
    }

    Writer& operator<<(int a) {
        int many = 0;
        if (a < 0) {
            a = -a;
            putchar('-');
        }

        do {
            digit_buffer[many++] = a % 10 + '0';
            a /= 10;
        } while (a > 0);
        for (int i = many - 1; i >= 0; --i)
            putchar(digit_buffer[i]);
        return *this;
    }

    Writer& operator<<(const char *s) {
        for (; *s; ++s)
            putchar(*s);
        return *this;
    }

    ~Writer() {
        m_stream.write(m_buffer.get(), m_pos);
    }

  private:
    void putchar(char c) {
        m_buffer[m_pos++] = c;
        if (m_pos == kBufferSize) {
            m_stream.write(m_buffer.get(), m_pos);
            m_pos = 0;
        }
    }

    static const int kBufferSize = 32768;
    ostream& m_stream;
    unique_ptr<char[]> m_buffer;
    char digit_buffer[30];
    int m_pos;
};

class Reader {
  public:
    Reader(istream& stream):
            m_stream(stream),
            m_pos(kBufferSize - 1),
            m_buffer(new char[kBufferSize]) {
        next();
    }

    Reader& operator>>(int& value) {
        value = 0;
        bool sign = false;

        while ((current() < '0' || current() > '9') && current() != '-')
            next();

        if (current() == '-') {
            sign = true;
            next();
        }
        while (current() >= '0' && current() <= '9') {
            value = value * 10 + current() - '0';
            next();
        }
        if (sign)
            value = -value;
        return *this;
    }

  private:
    const int kBufferSize = 32768;

    char current() {
        return m_buffer[m_pos];
    }

    void next() {
        if (++m_pos == kBufferSize) {
            m_stream.read(m_buffer.get(), kBufferSize);
            m_pos = 0;
        }
    }

    istream& m_stream;
    int m_pos;
    unique_ptr<char[]> m_buffer;
};

struct Edge {
    int from, to, weight;

    bool operator<(const Edge& that) const {
        return weight < that.weight;
    }
};

class DisjointSet {
  public:
    DisjointSet(unsigned size):
        m_anc(size) {
        for (unsigned i = 0; i < size; ++i)
            m_anc[i] = i;
    }

    bool merge(unsigned x, unsigned y) {
        x = anc(x);
        y = anc(y);
        if (x == y)
            return false;
        m_anc[y] = x;
        return true;
    }

  private:
    unsigned
        anc(unsigned x) {
        if (m_anc[x] == x)
            return x;
        return (m_anc[x] = anc(m_anc[x]));
    }
    vector<unsigned> m_anc;
};

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

    Reader input(cin);
    Writer output(cout);

    int N, M; input >> N >> M;
    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i)
        input >> edges[i].from >> edges[i].to >> edges[i].weight;

    sort(edges.begin(), edges.end());
    DisjointSet D(N);

    int total = 0;
    vector<pair<int, int>> answer;
    answer.reserve(N - 1);
    for (auto &edge : edges)
        if (D.merge(edge.from - 1, edge.to - 1)) {
            answer.emplace_back(edge.from, edge.to);
            total += edge.weight;
        }

    output << total << "\n";
    output << answer.size() << "\n";
    for (auto &p : answer)
        output << p.first << " " << p.second << "\n";
}