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

const int maxn = 200001;

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

struct comp {
    bool operator() (const edge &a, const edge &b)
    { return b.c > a.c; }
};

bool vnew[maxn];
vector<edge> enew;
multiset<edge, comp> S;
multiset<edge>::iterator it;

int main()
{
    int x, y, c, ct = 0, N, M, k = 1;
    in >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        in >> x >> y >> c;
        S.insert(edge(x, y, c));
    }
    vnew[S.begin()->u] = true;
    while (k < N)
    {
        for (it = S.begin(); it != S.end(); it++)
        {
            int u = it->u; int v = it->v;
            if (vnew[u] && !vnew[v])
            {
                vnew[v] = true;
                enew.push_back(edge(u, v));
                ct += it->c;
                S.erase(it);
            }
            else if (vnew[v] && !vnew[u])
            {
                vnew[u] = true;
                enew.push_back(edge(v, u));
                ct += it->c;
                S.erase(it);
            }
            else continue;
            break;
        }
        ++k;
    }
    out << ct << '\n';
    out << enew.size() << '\n';
    for (int i = 0; i < enew.size(); i++)
        out << enew[i].u << ' ' << enew[i].v << '\n';
    return 0;
}