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

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

const int MAX_SIZE = 200000;
const int MAX_EDGES = 400000;

int startNodes[MAX_EDGES + 1];
int endNodes[MAX_EDGES + 1];
int edgeCost[MAX_EDGES + 1];
int indexes[MAX_EDGES + 1];
int disjointTree[MAX_SIZE + 1];

bool comp(int i, int j) {
    return edgeCost[i] < edgeCost[j];
}

int findRoot(int startNode) {
    int root = startNode;
    while (disjointTree[root] != 0) {
        root = disjointTree[root];
    }
    int currentNode = startNode;
    while (disjointTree[currentNode] != 0) {
        int aux = currentNode;
        currentNode = disjointTree[currentNode];
        disjointTree[aux] = root;
    }
    return root;
}

int main() {
    int noNodes, noEdges;
    fin >> noNodes >> noEdges;
    for (int i = 1; i <= noEdges; ++i) {
        indexes[i] = i;
        fin >> startNodes[i] >> endNodes[i] >> edgeCost[i];
    }
    sort(indexes + 1, indexes + 1 + noEdges, comp);
    vector<int> minCostTree[MAX_SIZE + 1];
    int minCost = 0, minCostTreeEdges = 0;
    for (int i = 1; i <= noEdges; ++i) {
        if (findRoot(startNodes[indexes[i]]) != findRoot(endNodes[indexes[i]])) {
            minCost += edgeCost[indexes[i]];
            disjointTree[findRoot(endNodes[indexes[i]])] = findRoot(startNodes[indexes[i]]);
            minCostTree[startNodes[indexes[i]]].push_back(endNodes[indexes[i]]);
            ++minCostTreeEdges;
        }
    }
    fout << minCost << '\n' << minCostTreeEdges << '\n';
    for (int i = 1; i <= noNodes; ++i) {
        for (vector<int>::iterator it = minCostTree[i].begin(); it < minCostTree[i].end(); ++it) {
            fout << i << ' ' << *it << '\n';
        }
    }
    return 0;
}