#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct edge {
    int x, y, c;

    bool operator<(const edge& aux) {
        return c < aux.c;
    }
};

int p[200005], h[200005];
vector<pair<int, int>> adj[200005];
int n, m, x, y, c;
int cmin;
vector<pair<int, int>> ans;
edge edges[200005];

int Find(int x) {
    int rx = x;
    while (rx != p[rx]) {
        rx = p[rx];
    }

    while (x != rx) {
        int tmp = p[x];
        p[x] = rx;
        x = tmp;
    }

    return rx;
}

void Union(int x, int y) {
    int rx = Find(x);
    int ry = Find(y);

    if (h[rx] < h[ry]) {
        p[rx] = ry;
    } else {
        p[ry] = rx;
    }

    if (h[rx] == h[ry])
        h[rx]++;
}

void kruskal() {
    int k = 0;

    for (int i = 1; i <= m && k < n - 1; i++) {
        if (Find(edges[i].x) != Find(edges[i].y)) {
            Union(edges[i].x, edges[i].y);
            ans.push_back({edges[i].x, edges[i].y});
            cmin += edges[i].c;
            k++;
        }
    }

}
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    in >> n >> m;
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        h[i] = 1;
    }

    for (int i = 1; i <= m; i++) {
        in >> x >> y >> c;
        edges[i].x = x;
        edges[i].y = y;
        edges[i].c = c;
    }

    sort(edges + 1, edges + m + 1);

    kruskal();

    out << cmin << '\n' << ans.size() << '\n';
    for (auto it : ans) {
        out << it.first << " " << it.second << '\n';
    }
    return 0;
}