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

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++)
            for (int j = 1; j <= n; j++)
                if (ocupat[j] == 0 && minim > cost[arbore[i]][j])
                {
                    minim = cost[arbore[i]][j];

                    x = arbore[i];

                    y = j;
                }

        lista[x].push_back(y);

        lista[y].push_back(x);

        s += cost[x][y];

        ocupat[y] = 1;

        arbore.push_back(y);
    }

    fout << s << "\n";

    queue<int>drum;

    drum.push(1);

    vector<pair<int, int>> add;

    while (!drum.empty())
    {
        int top = drum.front();

        liber[top] = 1;

        for (int i = 0; i < lista[top].size(); i++)
            if (liber[lista[top][i]] == 0)
            {
                drum.push(lista[top][i]);

                add.push_back({ top ,lista[top][i] });

                s += cost[top][lista[top][i]];
            }

        drum.pop();
    }

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