#include <fstream>
#include <vector>
#include <queue>
using namespace std;
// Algoritmul lui Prim
ifstream in("apm.in");
ofstream out("apm.out");

const int maxn = 200001;

struct edge {
    edge(int v, int c) { this->v = v; this->c = c; }
    int v, c;
};

struct comp {
    bool operator() (const edge &a, const edge &b)
    { return b.c < a.c; }
};
priority_queue<edge, vector<edge>, comp> qu[maxn];
vector<edge> solutie;
int H[maxn];  // vector de tati

int father(int x)
{
    if (x != H[x])
        return father(H[x]);
    return H[x];
}

int main()
{
    int N, M, x, y, c, ct = 0, v;
    in >> N >> M; solutie.reserve(N);
    for (int i = 1; i <= N; i++) H[i] = i;
    for (int i = 1; i <= M; i++)
    {
        in >> x >> y >> c;
        qu[x].push(edge(y, c));
        qu[y].push(edge(x, c));
    }
    for (int i = 1; i <= N; i++)
    {
        if (!qu[i].empty())
        {
            v = qu[i].top().v;
            if (father(i) != father(v))
            {
                ct += qu[i].top().c;
                solutie.push_back( edge(i, v) );
                H[father(v)] = father(i);
                if (!qu[v].empty() && qu[v].top().v == i) qu[v].pop();
            }
        }
    }
    out << ct << '\n';
    out << solutie.size() << '\n';
    for (int i = 0; i < solutie.size(); i++)
        out << solutie[i].v << ' ' << solutie[i].c << '\n';

    return 0;
}