#include <fstream>
#include <queue>
#include <deque>
#include <vector>
using namespace std;

const int INF = 1 << 30;

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    int n, m;
    fin >> n >> m;

    vector<vector<pair<int,int>>> adj(n+1);

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;

        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    int cost_total = 0;
    vector<pair<int,int>> muchii_folosite;

    vector<bool> in_arbore(n+1, false);

    vector<pair<int,int>> cost_de_legatura(n+1, {INF, -1});

    // cost...[i] = {c, j} --> {c, {i, j}}

    priority_queue<
        //   cost,    nod, vecin
        pair<int,pair<int,int>>,
        deque<pair<int,pair<int,int>>>,
        greater<pair<int,pair<int,int>>>> q;

    int start = 1;
    in_arbore[start] = true;

    for (auto p : adj[start]) {
        cost_de_legatura[p.first] = {p.second, start};
        q.push({p.second, {p.first, start}});
    }

    while ((int)muchii_folosite.size() < n-1) {
        int nod_min = -1;
        int cost_min = INF;
        int vecin = -1;

        while (nod_min == -1) {
            auto p = q.top();
            q.pop();
            int nod = p.second.first;
            vecin = p.second.second;
            cost_min = p.first;

            if (!in_arbore[nod]
                && cost_de_legatura[nod].first == cost_min)
            {
                nod_min = nod;
            }
        }

        cost_total += cost_min;
        in_arbore[nod_min] = true;
        muchii_folosite.push_back({nod_min, vecin});

        for (auto p : adj[nod_min]) {
            int nod = p.first;
            int cost = p.second;

            if (cost_de_legatura[nod].first > cost) {
                cost_de_legatura[nod] = {cost, nod_min};
                q.push({cost, {nod, nod_min}});
            }
        }
    }

    fout << cost_total << '\n';
    fout << n-1 << '\n';

    for (auto m : muchii_folosite)
        fout << m.first << ' ' << m.second << '\n';

    return 0;
}