#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 666013;
const char out[2][4]{ "NO", "YES" };
#define all(a) a.begin(), a.end()
using ll = long long;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m;
struct edge {
    int u, v, w;
    bool operator<(const edge& other) const {
        return w < other.w;
    }
};
vector<edge> edges;

struct dsu {
    int size, components;
    dsu(int size) {
        this->size = components = size;
        t.resize(size + 1);
        iota(t.begin(), t.end(), 0);
        r.assign(size + 1, 1);
    }
    int find(int x) {
        return t[x] == x ? x : (t[x] = find(t[x]));
    }
    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        if (r[x] < r[y]) {
            swap(x, y);
        }
        t[y] = x;
        r[x] += r[y];
        r[y] = 0;
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
private:
    vector<int> t, r;
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fin >> n >> m;
    edges.reserve(m);
    for (int i = 1; i <= m; ++i) {
        edge e;
        fin >> e.u >> e.v >> e.w;
        edges.push_back(e);
    }
    sort(all(edges));
    dsu tree(n);
    vector<pair<int, int>> selected;
    ll cost = 0;
    for (auto& e : edges) {
        if (!tree.connected(e.u, e.v)) {
            tree.merge(e.u, e.v);
            selected.push_back({ e.u, e.v });
            cost += e.w;
        }
        if (selected.size() == n - 1) {
            break;
        }
    }
    fout << cost << nl << n - 1 << nl;
    for (auto& e : selected) {
        fout << e.first << sp << e.second << nl;
    }
}