#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 main()
{
    int N, M, x, y, c, ct = 0, v;
    in >> N >> M; solutie.reserve(N);
    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())
        {
            ct += qu[i].top().c;
            v = qu[i].top().v;
            solutie.push_back( edge(i, v) );
            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;
}