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

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

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

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

int n;
vector<PII> G[nMAX];

auto cmp = [](const PII &x, const PII &y)
{
    if (!(x.first < y.first))
        return 1;
    return 0;
};

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

    return;
}

void load_graph()
{
    int m = 0;

    f >> n >> m;

    int x = 0, y = 0, c = 0;
    for (int i = 1; i <= m; ++i)
    {
        f >> x >> y >> c,
            add_edge(x, y, c);
    }

    return;
}

int main()
{
    load_graph();

    vector<int> d((n + 1), INF);
    vector<bool> completed((n + 1), false);
    vector<int> help((n + 1), 0);

    d[1] = 0, completed[1] = true;

    priority_queue<PII, vector<PII>, decltype(cmp)> H(cmp);
    H = {};

    for (const PII &e : G[1])
        if (e.first < d[e.second])
            d[e.second] = e.first, help[e.second] = 1, H.push(e);

    int total_cost = 0;

    while (!H.empty())
    {
        while (!H.empty() && completed[H.top().second])
            H.pop();

        if (H.empty())
            break;

        int node = H.top().second;
        total_cost += H.top().first;

        H.pop();
        completed[node] = true;

        for (const PII &it : G[node])
            if (!completed[it.second])
                if (it.first < d[it.second])
                    d[it.second] = it.first, help[it.second] = node, H.push(it);
    }

    g << total_cost << '\n'
      << (n - 1) << '\n';
    for (int i = 2; i <= n; ++i)
        g << i << ' ' << help[i] << '\n';

    return 0;
}