#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define SIZE 200005

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct                          muchie
{
    int                         x;
    int                         y;
    int                         cost;
};

int                             cmp(muchie a, muchie b)
{
    return (a.cost < b.cost);
}

void                            citire(int &n, int &m, vector<muchie> &myvector)
{
    muchie                      to_beread;

    f >> n >> m;
    for (int i = 0; i < m; i++)
    {
        f >> to_beread.x;
        f >> to_beread.y;
        f >> to_beread.cost;
        myvector.push_back(to_beread);
    }
    sort(myvector.begin(), myvector.end(), cmp);
}

void                            initialize(int n, int v[SIZE])
{
    for (int i = 1; i <= n; i++)
        v[i] = i;
}

void                            solve(int n, int m, vector <muchie> foo)
{
    int                         aux;
    int                         j;
    int                         cost_total;
    int                         v[SIZE];
    vector <pair <int, int> >   solution;

    initialize(n, v);
    cost_total = 0;
    j = 0;
    for (int i = 1; i < n; i++)
    {
        if (v[foo[j].x] == v[foo[j].y])
            i--;
        else
        {
            solution.push_back(make_pair(foo[j].x, foo[j].y));
            cost_total += foo[j].cost;
            aux = v[foo[j].y];
            for (int k = 1; k <= n; k++)
            {
                if (v[k] == aux)
                    v[k] = v[foo[j].x];
            }
        }
        j++;
    }
    g << cost_total << '\n' << n - 1 << '\n';
    for (int i = 0; i < solution.size(); i++)
        g << solution[i].second << ' ' << solution[i].first << '\n';
}

int main()
{
    int                 n, m;
    vector <muchie>     foo;

    citire(n, m, foo);
    solve(n, m, foo);
    return 0;
}