// https://www.infoarena.ro/problema/apm - Szücs Patrik - Kevin
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

struct edge
{
    int from, to, cost;

    bool operator<(const edge &a) const
    {
        return cost > a.cost;
    }
};

int main()
{
    int n, m;

    ifstream in("apm.in");
    in >> n >> m;

    vector<vector<pair<int, int>>> graf(n + 1);
    while (m--)
    {
        int x, y, c;
        in >> x >> y >> c;

        graf[x].push_back({y, c});
        graf[y].push_back({x, c});
    }
    in.close();

    priority_queue<edge> pq;
    pq.push({0, 1, 0});
    vector<bool> vis(n + 1);

    vector<pair<int, int>> ans;
    int s = 0;

    while (!pq.empty())
    {
        edge e = pq.top();
        pq.pop();

        if (ans.size() == n - 1)
            break;

        if (vis[e.to])
            continue;
        vis[e.to] = true;

        s += e.cost;
        if (e.from != 0)
            ans.push_back({e.from, e.to});

        for (auto &[next, cost] : graf[e.to])
        {
            if (!vis[next])
                pq.push({e.to, next, cost});
        }
    }

    ofstream out("apm.out");
    out << s << '\n'
        << ans.size();
    for (auto &[a, b] : ans)
        out << '\n'
            << a << ' ' << b;

    out.close();
    return 0;
}