#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;
};

class Heap {
  public:
    Heap(int size, int value):
        m_value(size, value),
        m_index(size),
        m_heap(size),
        m_size(size)
    {
        for (int i = 0; i < size; ++i)
            m_index[i] = m_heap[i] = i;
    }

    int value(int index) {
        return m_value[index];
    }

    bool empty() const {
        return m_size == 0;
    }

    void update(int index, int value) {
        int where = m_index[index];
        m_value[index] = value;
        while (where != 0 && m_value[m_heap[where]] < m_value[m_heap[(where - 1)/ 2]]) {
            swap(m_index[m_heap[where]], m_index[m_heap[(where - 1) / 2]]);
            swap(m_heap[where], m_heap[(where - 1) / 2]);
            where /= 2;
        }
    }

    int pop() {
        --m_size;
        swap(m_index[m_heap[m_size]], m_index[m_heap[0]]);
        swap(m_heap[m_size], m_heap[0]);
        int node = 0;
        while (true) {
            int left = node * 2 + 1;
            int right = node * 2 + 2;
            int next = node;
            if (left < m_size && m_value[m_heap[left]] < m_value[m_heap[next]])
                next = left;
            if (right < m_size && m_value[m_heap[right]] < m_value[m_heap[next]])
                next = right;
            if (node == next)
                break;
            swap(m_index[m_heap[node]], m_index[m_heap[next]]);
            swap(m_heap[node], m_heap[next]);
            node = next;
        }
        return m_heap[m_size];
    }

    bool used(int index) const {
        return m_index[index] >= m_size;
    }

  private:
    vector<int> m_value, m_index, m_heap;
    int m_size;
};

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

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

    int N, M; input >> N >> M;
    vector< vector< pair<int, int> > > edges(N);
    for (int i = 0; i < M; ++i) {
        int from, to, weight; input >> from >> to >> weight;
        --from; --to;
        edges[from].emplace_back(to, weight);
        edges[to].emplace_back(from, weight);
    }

    vector<int> how(N, -1);
    Heap H(N, numeric_limits<int>::max());

    int total = 0;
    vector< pair<int, int> > answer;
    while (!H.empty()) {
        int node = H.pop();

        if (how[node] != -1) {
            total += H.value(node);
            answer.emplace_back(how[node], node);
        }

        for (auto &edge : edges[node])
            if (!H.used(edge.first) && H.value(edge.first) > edge.second) {
                H.update(edge.first, edge.second);
                how[edge.first] = node;
            }
    }

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