#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 500100
using namespace std;

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

int n, m;

pair< int, pair<int, int> > edgeArray[NMAX];

int father[NMAX], child[NMAX], dim[NMAX], nextNode[NMAX];

bool samePartition(int x, int y) {
    return (father[x] == father[y]);
}

void merge(int x, int y) {
    dim[father[y]] += dim[father[x]];
    nextNode[child[father[y]]] = father[x];
    child[father[y]] = child[father[x]];
    int currentNode = father[x];
    int lastNode = child[father[x]];
    while(currentNode != lastNode) {
        father[currentNode] = father[y];
        currentNode = nextNode[currentNode];
    }
    father[currentNode] = father[y];
}

pair<int, int> answer[NMAX];

int main() {

    f >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        f >> x >> y >> cost;
        x --;
        y --;
        pair<int, int> p1(x, y);
        edgeArray[i].first = cost;
        edgeArray[i].second = p1;
    }

    for (int i = 0; i < n; ++i) {
        father[i] = i;
        dim[i] = 1;
        nextNode[i] = i;
        child[i] = i;
    }
    sort(edgeArray, edgeArray + m);
    int cost = 0;
    int nrElem = 0;
    for (int i = 0; nrElem < n - 1; ++i) {
        int node1 = edgeArray[i].second.first;
        int node2 = edgeArray[i].second.second;
        if (!samePartition(node1, node2)) {
            cost += edgeArray[i].first;
            answer[nrElem] = edgeArray[i].second;
            nrElem ++;
            if (dim[father[node1]] < dim[father[node2]]) {
                merge(node1, node2);
            } else {
                merge(node2, node1);
            }
        }
    }

    g << cost << "\n";
    g << nrElem << "\n";
    for (int i = 0; i < nrElem; ++i) {
        g << answer[i].first + 1 << " " << answer[i].second + 1 << "\n";
    }

    return 0;
}