#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct edge {
    int node1, node2, cost;
};

const int MAXN = 2e5 + 5, MAXM = 4e5 + 5;
int nrNodes, nrEdges, tree[MAXN];

bool compareByCost(edge edgeNr1, edge edgeNr2) {
    return edgeNr1.cost < edgeNr2.cost;
}

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

int main() {
    fin >> nrNodes >> nrEdges;
    vector <edge> graph(nrEdges);
    for (int i = 0; i < nrEdges; i++) {
        fin >> graph[i].node1 >> graph[i].node2 >> graph[i].cost;
    }
    for (int i = 1; i <= nrNodes; i++) {
        tree[i] = i;
    }

    ll totalCost = 0;
    vector<pair<int, int> > minTree;
    sort(graph.begin(),  graph.end(), compareByCost);
    for (int i = 0; i < nrEdges; i++) {
        int root1 = findRoot(graph[i].node1);
        int root2 = findRoot(graph[i].node2);
        if (root1 != root2) {
            totalCost += graph[i].cost;
            minTree.push_back(make_pair(graph[i].node1, graph[i].node2));
            tree[min(root1, root2)] = tree[max(root1, root2)];
        }
    }

    fout << totalCost << "\n" << nrNodes - 1 << "\n";
    for (int i = 0; i < nrNodes - 1; i++) {
        fout << minTree[i].first << " " << minTree[i].second << "\n";
    }
    return 0;
}