#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int x, y, c;
};

bool cmp(Edge a, Edge b) {
    return a.c < b.c;
}

struct DSU {
    vector<int> h, p;
    DSU(int n) {
        h.resize(n + 1);
        p.resize(n + 1);
        for(int i = 1; i <= n; i++) {
            h[i] = 1;
            p[i] = i;
        }
    }
    int Find(int x) {
        if (x != p[x]) p[x] = Find(p[x]);
        return p[x];
    }
    void Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        if (x != y) {
            if (h[x] < h[y]) swap(x, y);
            p[y] = x;
            h[x] += h[y];
        }
    }
};

pair<int, vector<pair<int, int>>> computeAPM(int n, int m, vector<Edge> &edges) {
    sort(edges.begin(), edges.end(), cmp);
    int apm = 0;
    vector<pair<int, int>> mst_edges;
    DSU dsu(n);
    for (auto &edge : edges) {
        if (dsu.Find(edge.x) != dsu.Find(edge.y)) {
            apm += edge.c;
            dsu.Union(edge.x, edge.y);
            mst_edges.push_back({edge.x, edge.y});
        }
    }
    return {apm, mst_edges};
}

int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m;
    f >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        f >> edges[i].x >> edges[i].y >> edges[i].c;
    }
    auto [apm, mst_edges] = computeAPM(n, m, edges);
    g << apm << '\n';
    g << mst_edges.size() << '\n';
    for (const auto &edge : mst_edges) {
        g << edge.first << ' ' << edge.second << '\n';
    }
    return 0;
}