#include <iostream>
#include <algorithm>

const int MAX_N = 2e5;
const int MAX_M = 4e5;

struct Edge {
    int u, v, c;
    bool used = false;

    void read() {
        scanf("%d %d %d", &u, &v, &c);
    }
};

struct Dsu {
    struct Node {
        int parent;
        int size;
    };

    Node t[MAX_N + 1];

    void init() {
        for (int i = 1; i <= MAX_N; i++) {
            t[i] = { i, 1 };
        }
    }

    int find(int node) {
        if (t[node].parent == node) {
            return node;
        }

        t[node].parent = find(t[node].parent);
        return t[node].parent;
    }

    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;

        if (t[u].size < t[v].size) {
            std::swap(u, v);
        }

        t[v].parent = u;
        t[u].size += t[v].size;
    }
};

int n, m;
Edge edges[MAX_M];
Dsu dsu;

void read_edges() {
    for (int i = 0; i < m; i++) {
        edges[i].read();
    }
}

void sort_edges() {
    std::sort(edges, edges + m, [](Edge a, Edge b) {
        return a.c < b.c;
    });
}

int kruskal() {
    int cost = 0;

    for (int i = 0; i < m; i++) {
        auto& [u, v, c, used] = edges[i];

        if (dsu.find(u) == dsu.find(v))
            continue;

        dsu.unite(u, v);
        cost += c;
        used = true;
    }

    return cost;
}

void print_used_edges() {
    for (int i = 0; i < m; i++) {
        auto [u, v, c, used] = edges[i];
        if (used) {
            printf("%d %d\n", u, v);
        }
    }
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d", &n, &m);
    read_edges();
    sort_edges();
    dsu.init();
    printf("%d\n%d\n", kruskal(), n - 1);
    print_used_edges();
}