#include <iostream>
#include <set>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, rang[200001], edges[200001], x, y, c, total_cost;
set <pair <int, pair <int, int>>> v;
vector <pair <int, int>> tree;

int find_root(int a) {
    int node = a;
    while (edges[node] != node)
        node = edges[node];

    while (edges[a] != a) {
        int aux = edges[a];
        edges[a] = node;
        a = aux;
    }
    return node;
}

void unite(int x, int y) {
    if (rang[x] > rang[y])
        edges[y] = x;
    else
        edges[x] = y;

    if (rang[x] == rang[y])
        ++rang[y];
}

int main() {
    fin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        edges[i] = i;
        rang[i] = 1;
    }

    for (int i = 1; i <= m; ++i) {
        fin >> x >> y >> c;
        v.insert(make_pair(c, make_pair(x, y)));
    }

    for (auto it = v.begin(); it != v.end(); ++it) {
        int cost = it->first, a = it->second.first, b = it->second.second;
        if (find_root(a) != find_root(b)) {
            total_cost += cost;
            unite(find_root(a), find_root(b));
            tree.push_back(make_pair(a, b));
        }
    }

    fout << total_cost << '\n' << tree.size() << '\n';
    for (auto it = tree.begin(); it != tree.end(); ++it)
        fout << it->first << " " << it->second << '\n';
}