#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});

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

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

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

        for (int i = 1; i <= n; ++i) {
            if (!in_arbore[i]) {
                auto p = cost_de_legatura[i];
                if (p.first < cost_min) {
                    nod_min = i;
                    cost_min = p.first;
                    vecin = p.second;
                }
            }
        }

        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};
        }
    }

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

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

    return 0;
}