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

using namespace std;

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

struct nod
{
    int s, d, pret;
};

vector<pair<int, int>> add;

int main()
{
    int n, m, s = 0, a, b, c;

    fin >> n >> m;

    vector<int> arbore;

    vector<int> ocupat(n + 1, 0);

    vector<int> liber(n + 1, 0);

    vector<vector<int> > cost(n + 1, vector<int>(n + 1, 2147483647));

    vector<vector<int> > lista(n + 1, vector<int>());

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

        cost[a][b] = cost[b][a] = c;
    }

    arbore.push_back(1);

    ocupat[1] = 1;

    while (arbore.size() != n) {
        int minim = 2147483647, x, y;

        for (int i = 0; i < arbore.size(); i++) {
            x = arbore[i];

            for (int j = 1; j <= n; j++)
                if (ocupat[j] == 0 && minim > cost[arbore[i]][j]) {
                    minim = cost[arbore[i]][j];
                    y = j;
                }
        }

        s += minim;

        lista[x].push_back(y);

        lista[y].push_back(x);

        ocupat[y] = 1;

        arbore.push_back(y);

        add.push_back({ x, y });
    }

    fout << s << "\n";

    fout << n - 1 << "\n";
    for (int i = 0; i < n - 1; ++i)
        fout << add[i].first << " " << add[i].second << "\n";
}