#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

const int NMAX = 200005;
const int MMAX = 400005;

struct EDGE {
    int a, b, c;
} edge[MMAX], e[NMAX];

struct compareCost {
    bool operator()(EDGE edge1, EDGE edge2) {
        return edge1.c > edge2.c;
    }
};

int n, m, edges_num, tree_cost, parent[NMAX], nodeRank[NMAX];
priority_queue<EDGE, vector<EDGE>, compareCost> Q;

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

int validEdge(EDGE edge) {
    int node1Root = findRoot(edge.a), node2Root = findRoot(edge.b);
    cout << "#" << edges_num + 1 << endl;
    cout << "Muchie (" << edge.a << ',' << edge.b << ')' << endl;
    cout << "Radacina " << edge.a << ": " << node1Root << endl;
    cout << "Radacina " << edge.b << ": " << node2Root << endl << endl;
    if (node1Root != node2Root) {
        return 1;
    }
    return 0;
}

void uniteTrees(int node1, int node2) {
    int node1Root = findRoot(node1), node2Root = findRoot(node2);
    if (nodeRank[node1Root] > nodeRank[node2Root]) {
        parent[node2Root] = node1Root;
    } else {
        parent[node1Root] = node2Root;
        if (nodeRank[node1Root] == nodeRank[node2Root]) {
            ++nodeRank[node2Root];
        }
    }
}

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> edge[i].a >> edge[i].b >> edge[i].c;
        Q.push(edge[i]);
    }
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }
    while (!Q.empty()) {
        EDGE act_edge = Q.top();
        Q.pop();
        if (validEdge(act_edge)) {
            e[++edges_num] = act_edge;
            tree_cost += act_edge.c;
            uniteTrees(act_edge.a, act_edge.b);
        }
    }
    fout << tree_cost << endl;
    fout << edges_num << endl;
    for (int i = 1; i <= edges_num; ++i) {
        fout << e[i].a << ' ' << e[i].b << endl;
    }
    return 0;
}