#include <fstream>
#include <algorithm> //nlogn
#include <vector>

#define NMAX 105

using namespace std;

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

struct Muchie
{
    int x, y;
    bool operator<(const Muchie m) const
    {
        if (m.x != x)
            return x < m.x;
        return y < m.y;
    }
};

int n, m;
vector<pair<int, Muchie>> v;
vector<int> l[NMAX];
int comp_conex[NMAX]; //comp_conex[i] = componenta conexa in care se afla nodul i
int suma; //suma minima
vector<Muchie> rez; //muchiile arborelui partial
int i, j;

void dfs(int, int, int);

int main()
{
    fin >> n >> m;
    for (i = 1; i <= m; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        v.push_back({ cost, {x, y} });
        l[x].push_back(y);
        l[y].push_back(x);
    }

    sort(v.begin(), v.end());

    for (i = 1; i <= n; ++i)
        comp_conex[i] = i; //la inceput, fiecare nod izolat

    int count = 0;
    for (i = 0; count < n - 1; ++i) //un arbore are exact n-1 muchii
    {
        //iau muchia curenta de cost minim;
        int cost = v[i].first;
        int x = v[i].second.x;
        int y = v[i].second.y;
        if (comp_conex[x] != comp_conex[y])
        {
            count++;

            suma += cost;
            rez.push_back({ x, y });

            //leg x de y, deci vor fi in aceeasi componenta conexa
            int minim = min(comp_conex[x], comp_conex[y]);
            int maxim = max(comp_conex[x], comp_conex[y]);
            int nod = comp_conex[x] < comp_conex[y] ? y : x;
            dfs(nod, maxim, minim);
        }
    }

    fout << suma << '\n';
    fout << rez.size() << '\n';
    for (auto crt : rez)
        fout << crt.x << ' ' << crt.y << '\n';

    return 0;
}

void dfs(int vf, int a, int b)
{
    comp_conex[vf] = b;
    for (auto vfcrt : l[vf])
        if (comp_conex[vfcrt] == a)
            dfs(vfcrt, a, b);
}