#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 2e5;

using namespace std;

struct DSU {
    int par[NMAX + 5];
    int sz[NMAX + 5];

    void init(int n) {
        iota(par + 1, par + n + 1, 1LL);
        fill(sz + 1, sz + n + 1, 1LL);
    }

    inline int root(int x) {
        if (x == par[x]) return x;
        return par[x] = root(par[x]);
    }

    bool same(int a, int b) {
        return root(a) == root(b);
    }

    void unite(int a, int b) {
        a = root(a), b = root(b);
        if (a == b) return;

        if (sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        par[b] = a;
    }
};

DSU dsu;
vector<array<int, 3>> edges;
vector<pair<int, int>> take;
int n, m;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

#ifdef INFOARENA
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
#endif

    cin >> n >> m;

    for (int i = 0, u, v, w; i < m; ++i) {
        cin >> u >> v >> w;
        edges.push_back({w, u, v});
    }

    sort(all(edges));
    dsu.init(n);
    int cost = 0;
    for (auto &[w, u, v] : edges) {
        if (!dsu.same(u, v)) {
            cost += w;
            take.push_back({u, v});
            dsu.unite(u, v);
        }
    }

    cout << cost << '\n' << sz(take) << '\n';
    for (auto &[u, v] : take)
        cout << u << ' ' << v << '\n';
    return 0;
}