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

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


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> distance(N, numeric_limits<int>::max());
    vector<int> how(N, -1);
    vector<bool> used(N, false);
    set< pair<int, int> > S;
    S.emplace(0, 0);

    int total = 0;
    vector< pair<int, int> > answer;
    while (!S.empty()) {
        int node = S.begin()->second;
        S.erase(S.begin());
        used[node] = true;

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

        for (auto &edge : edges[node])
            if (!used[edge.first] && distance[edge.first] > edge.second) {
                S.erase(make_pair(distance[edge.first], edge.first));
                distance[edge.first] = edge.second;
                how[edge.first] = node;
                S.emplace(distance[edge.first], edge.first);
            }
    }

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