#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, father[nmax], rang[nmax], total_cost;

struct edge {
    int x;
    int y;
    int cost;
};

vector < edge > edges;

vector < pair < int, int > > results;

bool compare_function(const edge &a, const edge &b) {
    return a.cost < b.cost;
}

inline int find_root(int x) {
    int root;
    for (root = x; father[root] != root; root = father[root]);
    for (int y; father[x] != x;) {
        y = father[x];
        father[x] = root;
        x = y;
    }
    return root;
}

inline void unite(int x, int y) {
    if (rang[x] < rang[y])
        father[x] = y;
    else
        father[y] = x;
    if (rang[x] == rang[y])
        ++rang[x];
}

void make_for(int x, int y, int cost) {
    if (find_root(x) != find_root(y)) {
        unite(find_root(x), find_root(y));
        total_cost += cost;
        results.push_back(make_pair(x, y));
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
        rang[i] = 1;
    }
    int x, y, z;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y >> z;
        edge stuff = {x, y, z};
        edges.push_back(stuff);
    }
    sort(edges.begin(), edges.end(), compare_function);
    for (vector < edge > :: iterator it = edges.begin(); it != edges.end(); ++it)
        make_for((*it).x, (*it).y, (*it).cost);
    fout << total_cost << "\n" << results.size() << "\n";
    for (vector < pair < int, int > > :: iterator it = results.begin(); it != results.end(); ++it)
        fout << (*it).first << " " << (*it).second << "\n";
    return 0;
}