#include <bits/stdc++.h>

using namespace std;

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

struct Muchie {
    int n1, n2;
    int c;

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

int n, m;
int x, y, z;
vector<pair<int, int>> g[200001];
vector<pair<int, int>> apm;
bool viz[200001];
int cost;

void prim() {
    priority_queue<Muchie> pq;

    for (auto& x : g[1]) {
        pq.push({ 1, x.first, x.second });
    }
    viz[1] = 1;

    while (!pq.empty()) {
        auto t = pq.top();
        pq.pop();

        if (viz[t.n2]) {
            continue;
        }

        viz[t.n2] = 1;
        cost += t.c;
        apm.push_back({ t.n1, t.n2 });

        for (auto& x : g[t.n2]) {
            pq.push({ t.n2, x.first, x.second });
        }
    }
}

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

    prim();

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