#include <bits/stdc++.h>

using namespace std;

typedef tuple<int, int, int> edge;
#define cost(e) std::get<0>(e)
#define first(e) std::get<1>(e)
#define second(e) std::get<2>(e)

class Task {
public:
    void solve() {
        read_input();
        get_result();
        print_output();
    }

private:
    int n, m;

    // p[i] = parintele lui i de pe drumul minim de la source la nodul i
    vector<int> p;

    vector<int> rank;

    vector<edge> edges;

    vector<edge> apm_edges;

    int apm;

    void read_input() {
        cin >> n >> m;
        p = vector<int>(n + 1);
        rank = vector<int>(n + 1, 0);
        for (int i = 1; i <= m; ++i) {
            // citim muchii x -> y, de cost c
            int x, y, c;
            cin >> x >> y >> c;
            edges.push_back(edge(c, x, y));
        }
    }

    void get_result() {
        Kruskal();
    }

    int get_set(int node) {
        if (node != p[node]) {
            // path compression
            p[node] = get_set(p[node]);
        }
        return p[node];
    }

    void reunion_set(int x, int y) {
        int xRoot = get_set(x);
        int yRoot = get_set(y);
        if (rank[xRoot] > rank[yRoot]) {
            p[yRoot] = xRoot;
            return;
        }
        if (rank[xRoot] < rank[yRoot]) {
            p[xRoot] = yRoot;
            return;
        }
        p[xRoot] = yRoot;
        ++rank[yRoot];
    }

    void Kruskal() {
        sort(edges.begin(), edges.end());
        for (int i = 1; i <= n; ++i) {
            p[i] = i;
        }

        apm = 0;
        for (auto &e : edges) {
            int u = first(e);
            int v = second(e);
            int c = cost(e);
            if (get_set(u) != get_set(v)) {
                reunion_set(u, v);
                apm += c;
                apm_edges.push_back(e);
            }
        }
    }

    void print_output() {
        cout << apm << '\n';
        int s = apm_edges.size();
        cout << s << '\n';
        for (int i = 0; i < s; ++i) {
            cout << first(apm_edges[i]) << ' ' << second(apm_edges[i]) << '\n';
        }
    }
};

int main() {
    // din cauza ca fac redirectari, salvez starea lui cin si cout
    auto cin_buff = cin.rdbuf();
    auto cout_buff = cout.rdbuf();

    // las liniile urmatoare daca citesc din fisier
    ifstream fin("apm.in");
    cin.rdbuf(fin.rdbuf()); // save and redirect

    // las liniile urmatoare daca afisez in fisier
    ofstream fout("apm.out");
    cout.rdbuf(fout.rdbuf()); // save and redirect

    // aici este rezolvarea propriu-zisa
    Task *task = new Task();
    task->solve();
    delete task;

    // restore pentru cin si cout
    cin.rdbuf(cin_buff);
    cout.rdbuf(cout_buff);

    // obs. nu e nevoie sa inchid fisierele
    // cand se apeleaza destructorii pentru fin si fout se vor inchide

    return 0;
}