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

using namespace std;

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

const int NMAX = 200005;
int n, m, dad[NMAX], rang[NMAX], cost_total;

struct muchie {
    int x, y, c;
};
vector<muchie> muchii, apm;

bool operator< (muchie a, muchie b)
{
    return (a.c < b.c);
}

int do_find(int nod)
{
    if (nod != dad[nod])
    {
        int repr = do_find(dad[nod]);
        dad[nod] = repr;
        return repr;
    }
    else return nod;
}

void do_union(int x, int y)
{
    if (rang[x] < rang[y])
        dad[x] = y;
    else if (rang[x] > rang[y])
        dad[y] = x;
    else if (rang[x] == rang[y])
    {
        dad[x] = y;
        rang[y]++;
    }
}

int main()
{
    fin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        muchii.push_back({x, y, c});
    }
    sort(muchii.begin(), muchii.end());

    for (int i = 1; i <= n; i++)
    {
        dad[i] = i;
        rang[i] = 1;
    }
    for(int i = 0; i < muchii.size(); i++)
    {
        int repr_x = do_find(muchii[i].x);
        int repr_y = do_find(muchii[i].y);

        if (repr_x != repr_y)
        {
            cost_total += muchii[i].c;
            apm.push_back(muchii[i]);
            do_union(repr_x , repr_y);
        }
    }
    fout << cost_total << "\n";
    fout << n - 1 << "\n";
    for (muchie edge: apm)
    {
        fout << edge.x << " " << edge.y << "\n";
    }
    return 0;
}