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

using namespace std;
using PII = pair<int, int>;

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

static constexpr int nMAX = ((int)(2e5) + 1);
static constexpr int INF = ((int)(1e9));

int n;

vector<PII> G[nMAX];

auto cmp = [](const PII &a, const PII &b)
{
    if (!(a.first < b.first))
        return true;
    return false;
};
priority_queue<PII, vector<PII>, decltype(cmp)> H(cmp);

void add_edge(const int x, const int y, const int cost)
{
    G[x].push_back({cost, y}),
        G[y].push_back({cost, x});
    return;
}

void read()
{
    f.tie(nullptr);

    int m = 0;
    f >> n >> m;

    int u = 0, v = 0, cost = 0;
    for (int i = 1; i <= m; ++i)
        f >> u >> v >> cost,
            add_edge(u, v, cost);

    return;
}

int main()
{
    read();

    vector<int> best_length((n + 1), INF);
    vector<bool> used((n + 1), false);
    vector<int> t((n + 1), 0);

    const int S = 1;

    int total_cost = 0;

    best_length[S] = 0, used[S] = true;
    for (const PII &e : G[S])
        if (e.first < best_length[e.second])
            best_length[e.second] = e.first, t[e.second] = S, H.push(e);

    while (!H.empty())
    {
        while (!H.empty() && used[H.top().second] == true)
            H.pop();

        if (H.empty())
            break;

        int node = H.top().second;
        used[node] = true;
        total_cost += best_length[node];
        H.pop();

        for (const PII &e : G[node])
            if (!used[e.second])
                if (e.first < best_length[e.second])
                    best_length[e.second] = e.first, t[e.second] = node, H.push(e);
    }

    g << total_cost << '\n'
      << (n - 1) << '\n';
    for (int i = 2; i <= n; ++i)
        g << i << ' ' << t[i] << '\n', assert(t[i] != i), assert(t[i] > 0), assert(t[i] <= n);

    return 0;
}