#include <bits/stdc++.h>

using namespace std;

#define NMAX 200005

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

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

struct compare {
    inline bool operator()(const edge_t& edge1, const edge_t& edge2) {
        return edge1.cost < edge2.cost;
    }
};

int n, m;
vector<edge_t> edges;

int parent[NMAX];
int height[NMAX];

int find_parent(int x, vector<int> path) {
    while (x != parent[x]) {
        path.push_back(x);
        x = parent[x];
    }
    return x;
}

void unite(int x, int y) {
    vector<int> path_x, path_y;
    int parent_x = find_parent(parent[x], path_x);
    int parent_y = find_parent(parent[y], path_y);

    int height_x = height[parent_x];
    int height_y = height[parent_y];

    if (height_x < height_y) {
        parent[parent_x] = parent_y;
        for (int i = 0; i < (int)path_x.size(); ++i) {
            parent[path_x[i]] = parent_y;
        }
    } else {
        parent[parent_y] = parent_x;
        for (int i = 0; i < (int)path_y.size(); ++i) {
            parent[path_y[i]] = parent_x;
        }
    }
    if (height_x == height_y) {
        ++height[parent_x];
    }
}

int main()
{
    in >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        in >> x >> y >> cost;
        edges.push_back({x, y, cost});
    }

    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }

    sort(edges.begin(), edges.end(), compare());

    vector<pair<int, int>> mst_edges;

    long long sum = 0;
    for (int i = 0; i < edges.size(); ++i) {
        vector<int> path_x, path_y;
        int x = edges[i].x;
        int y = edges[i].y;
        int parent_x = find_parent(x, path_x);
        int parent_y = find_parent(y, path_y);

        if (parent_x == parent_y) continue;

        unite(x, y);
        int cost = edges[i].cost;
        sum += cost;
        mst_edges.push_back({y, x});
    }

    out << sum << "\n" << mst_edges.size() << "\n";
    for (int i = 0; i < mst_edges.size(); ++i) {
        out << mst_edges[i].first << " " << mst_edges[i].second << "\n";
    }
}