#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

using pii = pair<int, int>;
int n, m, x, y, z, apm_cost;
vector<pii> g[200000], apm;

struct Muchie {
    int x, p;
    int c;

    Muchie(int x, int p, int c) : x(x), p(p), c(c) {
    }

    bool operator<(const Muchie& other) const {
        return c > other.c;
    }
};

void prim() {
    priority_queue<Muchie> pq;
    pq.emplace(1, 0, 0);
    vector<bool> viz(n + 1);
    int cnt = 1;

    while (cnt <= n) {
        auto t = pq.top();
        pq.pop();
        if (viz[t.x]) {
            continue;
        }
        if (t.p) {
            apm.emplace_back(t.p, t.x);
            apm_cost += t.c;
        }
        viz[t.x] = 1;

        for (pii& x : g[t.x]) {
            if (!viz[x.first]) {
                pq.emplace(x.first, t.x, x.second);
            }
        }

        cnt++;
    }
}

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> z;
        g[x].push_back(make_pair(y, z));
        g[y].push_back(make_pair(x, z));
    }

    prim();

    fout << apm_cost << "\n" << apm.size() << "\n";
    for (pii& x : apm) {
        fout << x.first << " " << x.second << "\n";
    }
}