#include <fstream>
#include <vector>
#include <algorithm>
#define p pair <int, int>
using namespace std;

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

struct edge {
    pair<int, int> vert;
    int cost;
    edge (pair <int, int> v, int c):vert(v), cost(c) {};
};

vector <edge> E;
vector <int> tata(200000, 0), rang(200000, 0);

long n, m, x, y, w, s;

bool cmp (edge a, edge b) {
    if (a.cost > b.cost)
        return false;
    else
        return true;
}

int find (int nod) {
    if (tata[nod] == nod)
        return nod;
    else
        return find(tata[nod]);
}

void unesc (int root1, int root2) {
    if (rang[root1] > rang[root2]){
        tata[root2] = root1;
    }
    else {
        if (rang[root1] < rang[root2])
            tata[root1] = root2;
        else {
            tata[root1] = root2;
            rang[root2]++;
        }
    }
}

void make_set (int nod) {
    tata[nod] = nod;
    rang[nod] = 0;
}

void kruskal (int n) {
    vector <edge> arb;
    for (int i = 1; i <= n; i++) {
        make_set(i);
    }
    sort(E.begin(), E.end(), cmp);
    /*for (int i = 0; i < m; i++) {
        fout << E[i].vert.first << " " << E[i].vert.second << " " << E[i].cost << '\n';
    }*/
    for (int i = 0; i < m; i++) {
        int root1, root2;
        root1 = find(E[i].vert.first);
        root2 = find(E[i].vert.second);
        if (root1 != root2) {
            arb.push_back(E[i]);
            unesc(root1, root2);
        }
    }

    /*for (int i = 0; i < arb.size(); i++) {
        fout << arb[i].vert.first << " " << arb[i].vert.second << " " << arb[i].cost << '\n';
    }*/
    for (int i = 0; i < arb.size(); i++) {
        s += arb[i].cost;
    }
    fout << s << '\n' << arb.size() << '\n';
    for (int i = 0; i < arb.size(); i++) {
        fout << arb[i].vert.first << " " << arb[i].vert.second << '\n';
    }
}

int main () {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> w;
        E.push_back(edge(std::make_pair(x, y), w));
    }

    /*for (int i = 0; i < m; i++) {
        fout << E[i].vert.first << " " << E[i].vert.second << " " << E[i].cost << '\n';
    }*/
    kruskal(n);

}