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

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

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

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

int N, M;
vector<edge> G[NMAX];

auto cmp = [](const edge &a, const edge &b)
{
    if (!(a.first < b.first))
        return 1;

    return 0;
};
priority_queue<edge, vector<edge>, decltype(cmp)> H(cmp);

static inline void read_edge()
{
    int x = 0, y = 0, u = 0;
    f >> x >> y >> u;

    G[x].push_back({u, y});
    G[y].push_back({u, x});

    return;
}

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

    f >> N >> M;

    for (int i = 1; i <= M; ++i)
        read_edge();

    return;
}

int main()
{
    read();

    vector<int> ans, t = {};
    vector<bool> Sel = {};

    for (int i = 0; i <= N; ++i)
        ans.push_back(INF), t.push_back(-1), Sel.push_back(0);

    ans[1] = 0, Sel[1] = 1;
    for (auto &it : G[1])
        if (it.first < ans[it.second])
            ans[it.second] = it.first, t[it.second] = 1, H.push(it);

    int total_cost = 0;

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

        if (H.empty())
            break;

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

        H.pop();
        Sel[node] = 1;

        for (auto &it : G[node])
            if (it.first < ans[it.second])
                ans[it.second] = it.first, H.push({ans[it.second], it.second}), t[it.second] = node;
    }

    g << total_cost << '\n'
      << (N - 1) << '\n';

    for (int i = 2; i <= N; ++i)
        g << t[i] << ' ' << i << '\n';

    return 0;
}