# include <fstream>
# include <algorithm>
# include <vector>
using namespace std;

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

struct MUCHIE
{
    int x, y, cost;
} X[400010];
int n, m, sol, tata[200010];
vector < pair <int, int> > solv;

struct cmp
{
    inline bool operator ()(const MUCHIE &a, const MUCHIE &b) const
    {
        return a.cost < b.cost;
    }
};

int Find (int x)
{
    int r = x;
    while (tata[r])
        r = tata[r];
    int y = x;
    while (y != r)
    {
        int aux = tata[y];
        tata[y] = r;
        y = aux;
    }
    return r;
}

void Union (int x, int y)
{
    tata[x] = y;
}

int main ()
{
    f >> n >> m;
    for (int i = 1; i <= m; ++i)
        f >> X[i].x >> X[i].y >> X[i].cost;

    sort (X + 1, X + m + 1, cmp());
    for (int i = 1; i <= m; ++i)
    {
        int A = Find (X[i].x), B = Find (X[i].y);
        if (A != B) // daca nu sunt in aceeasi submultime, deci nu au cicluri
        {
            Union (A, B);
            sol += X[i].cost;
            solv.push_back (make_pair (A, B));
        }
    }

    g << sol << '\n';
    g << solv.size () << '\n';
    for (vector < pair <int, int> > :: iterator it = solv.begin (); it != solv.end (); ++it)
        g << it -> first << ' ' << it -> second << '\n';
    return 0;
}