#include <fstream>
#include <vector>
#include <queue>
#define mp make_pair

using namespace std;

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

const int Nmax = 200005;

struct graph
{
    int x;
    int y;
    int c;
};

struct comp
{
    bool operator()(graph X, graph Y)
    {
        return(X.c > Y.c);
    }
};

vector <int> dad(Nmax);

int Find (int x)
{
    if (dad[x] == x) return x;
    return dad[x] = Find (dad[x]);
}

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

int main()
{
    int n, m, nrm = 0, rez = 0;
    queue<pair <int, int>> Sol;
    priority_queue<graph, vector<graph>, comp> Q;

    in >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        graph Gr;

        Gr.x = x;
        Gr.y = y;
        Gr.c = c;

        Q.push(Gr);
    }

    for (int i = 1; i <= n; i++)
        dad[i] = i;

    while (nrm < n - 1)
    {
        int x = Q.top().x;
        int y = Q.top().y;
        int c = Q.top().c;

        int xx = Find(x);
        int yy = Find(y);

        if (xx != yy)
        {
            nrm++;
            rez = rez + c;
            Union(xx, yy);
            Sol.push(mp(x, y));
        }

        Q.pop();
    }

    out << rez << '\n';
    out << nrm << '\n';

    while (!Sol.empty())
    {
        out << Sol.front().first << ' ' << Sol.front().second << '\n';
        Sol.pop();
    }

    return 0;
}