#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m, costFinal;

vector <pair <int, int> > a[200005], ans;

vector <int> cost;

vector <bool> viz;

priority_queue < pair <int, int>, vector <pair<int, int> >, greater <pair <int, int> > > q;

void prim()
{
    q.push({0, 1});

    while (!q.empty()) {
        pair <int, int> nod = q.top();

        q.pop();

        if (viz[nod.second]) {
            continue;
        }

        viz[nod.second] = 1;

        costFinal += nod.first;

        for (auto vecin : a[nod.second]) {
            int next = vecin.first;
            int val = vecin.second;

            if (val < cost[next] && !viz[next]) {
                ans.push_back({nod.second, vecin.first});
                cost[next] = val;
                q.push({cost[next], next});
            }
        }
    }
}

int main()
{
    f >> n >> m;

    viz.resize(n + 1, 0), cost.resize(n + 1, 1e9);

    for (int i = 1; i <= m; ++i) {
        int x, y, z;

        f >> x >> y >> z;

        a[x].push_back({y, z});
        a[y].push_back({x, z});
    }

    prim();

    g << costFinal << '\n' << n - 1 << '\n';

    for (auto [a, b] : ans) {
        g << a << ' ' << b << '\n';
    }

    return 0;
}