#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie {
    int x, y;
    int cost;
};

struct nod {
    int rang = 0;
    nod* p;
};

nod* root(nod* a) {
    if (a -> p == nullptr) {
        return a;
    }
    return root(a -> p);
}

bool comp(muchie a, muchie b) {
    return a.cost < b.cost;
}

bool join(nod* a, nod* b) {

    a = root(a);
    b = root(b);

    if (a == b) {
        return false;
    }
    if (a -> rang > b -> rang) {
        b -> p = a;
    }
    if (b -> rang > a -> rang) {
        a -> p = b;
    }
    if (a -> rang == b -> rang) {
        b -> p = a;
        a -> rang += 1;
    }
    return true;
}

vector<muchie> v;
vector<nod*> n;
int N, M;

void read() {
    muchie a;
    fin >> N >> M;

    nod* no = new nod;
    no -> p = nullptr;
    no -> rang = 0;
    n.push_back(no);

    for (int i = 0; i < M; ++i) {
        fin >> a.x >> a.y >> a.cost;
        v.push_back(a);
        nod* no = new nod;
        no -> p = nullptr;
        no -> rang = 0;
        n.push_back(no);
    }
    sort(v.begin(), v.end(), comp);
}


int main()
{
    read();

    int cost = 0;

    vector<muchie> mu;

    for (int i = 0; i < M; ++i) {

        if (join(n[v[i].x], n[v[i].y])) {
            cost += v[i].cost;
            mu.push_back(v[i]);
        }
    }


    fout << cost << "\n" << mu.size() << "\n";
    for (int i = 0; i < mu.size(); ++i) {
        fout << mu[i].x << " " << mu[i].y << "\n";
    }

    return 0;
}