#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) + 4), 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;
};
priority_queue<PII, vector<PII>, decltype(cmp)> H(cmp);

static void add_edge(const int u, const int v, const int w)
{
    G[u].push_back({w, v}), G[v].push_back({w, u});
    return;
}

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

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

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

        add_edge(u, v, w);
    }

    return;
}

int main()
{
    read();

    vector<int> used((n + 1), false), d((n + 1), INF), parent((n + 1), (-1));

    used[1] = true, d[1] = 0, parent[1] = 0;
    for (const PII &it : G[1])
        if (it.first < d[it.second])
            d[it.second] = it.first, parent[it.second] = 1, H.push(it);

    int answer = 0;

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

        answer += H.top().first;

        int node = H.top().second;
        used[node] = true;

        H.pop();

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

    g << answer << '\n'
      << (n - 1) << '\n';

    vector<PII> edges = {};
    for (int i = 2; i <= n; ++i)
        edges.push_back({i, parent[i]});

    for (const PII &it : edges)
        g << it.first << ' ' << it.second << '\n';

    return 0;
}