// Kruskal's algorithm
//
// Find the minimum spanning tree (MST) - a subset of the original graph that
// contains all nodes, but only n - 1 edges with the property that the total
// weight of the edges is minimal.
//
// Complexity: O(M * logN)

#include <bits/stdc++.h>
using namespace std;

vector<int> parent;
vector<int> depth;

void make_set(int node)
{
    parent[node] = node;
    depth[node] = 0;
}

int find_set(int node)
{
    if (node == parent[node])
        return node;
    return parent[node] = find_set(parent[node]);
}

void union_sets(int node1, int node2)
{
    int root1 = find_set(node1);
    int root2 = find_set(node2);
    if (root1 == root2)
        return;

    if (depth[root1] < depth[root2])
        swap(root1, root2);
    if (depth[root1] == depth[root2])
        depth[root1]++;

    parent[root2] = root1;
}

struct Edge {
    int x, y, w;
    bool operator<(const Edge &other) const { return w < other.w; }
};

int n, m;
vector<Edge> edges;
vector<Edge> ans;

int kruskal()
{
    for (int i = 0; i < n; i++)
        make_set(i);

    int total_weight = 0;
    for (Edge e : edges) {
        if (find_set(e.x) != find_set(e.y)) {
            total_weight += e.w;
            union_sets(e.x, e.y);
            ans.push_back(e);
        }
    }
    return total_weight;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    cin >> n >> m;
    parent.resize(n);
    depth.resize(n);
    edges.resize(m);
    ans.clear();

    for (Edge &e : edges) {
        cin >> e.x >> e.y >> e.w;
        e.x--;
        e.y--;
    }
    sort(edges.begin(), edges.end());

    cout << kruskal() << '\n';
    cout << ans.size() << '\n';
    for (auto [x, y, _] : ans)
        cout << x + 1 << ' ' << y + 1 << '\n';

    return 0;
}