#include <fstream>
#include <vector>
#include <algorithm>

#define NMAX 200005


using namespace std;

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

struct muchie
{
    int x, y, c;
};

bool cmp(muchie m1, muchie m2)
{
    return m1.c < m2.c;
}

vector <int> G[NMAX], APM[NMAX];
vector <muchie> M;
vector <pair<int, int> > Rez;
int viz[NMAX];
int cost_total;

void df(int nod)
{
    if (viz[nod]) return;
    viz[nod] = 1;
    for (int i = 0; i < APM[nod].size(); ++i)
        df(APM[nod][i]);
}
int main()
{
    int n, m;
    int x, y, c;
    muchie mu;
    int nr_noduri = 0;

    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y >> c;
        G[x].push_back(y);
        G[y].push_back(x);

        mu.x = x; mu.y = y; mu.c = c;
        M.push_back(mu);
    }

    sort(M.begin(), M.begin() + m, cmp);

    for (int i = 0; i < m; ++i)
    {
        int nod1 = M[i].x;
        int nod2 = M[i].y;
        int cost = M[i].c;

        for (int j = 1; j <= n; ++j) viz[j] = 0;

        df(nod1);
        if (!viz[nod2])
        {
            APM[nod1].push_back(nod2);
            APM[nod2].push_back(nod1);
            Rez.push_back(make_pair(nod1,nod2));
            ++nr_noduri;
            cost_total += cost;
            if (nr_noduri == n) break;
        }
    }

    fout << cost_total << '\n';
    fout << n-1 << '\n';
    for (int i = 0; i < Rez.size(); ++i)
        fout << Rez[i].first << ' ' << Rez[i].second << '\n';
    return 0;
}