#include <iostream>
#include <algorithm>
#include <fstream>
#include <set>
using namespace std;
 
ifstream fin("apm.in");
ofstream fout("apm.out");
 
struct arch {
    int start, end, cost;
};
 
const int MAX_PEAKS = 200005;
const int MAX_ARCHES = 400005;
 
int noPeaks, noArches, representants[MAX_PEAKS];
set<pair<int, pair<int, int>>> arches;
 
int findRoot(int peak) {
    int root = representants[peak];
    while (root != representants[root]) {
        root = representants[root];
    }
    while (representants[peak] != root) {
        int aux = representants[peak];
        representants[peak] = root;
        peak = aux;
    }
    return root;
}

void unite(int start, int end) {
    representants[start] = representants[end];
}

int main() {
    fin >> noPeaks >> noArches;
    for (int i = 1 ; i <= noArches; ++i) {
        int start, end, cost;
        fin >> start >> end >> cost;
        pair<int, int> arch = make_pair(start, end);
        arches.insert(make_pair(cost, arch));
    }
    for (int i = 1; i <= noPeaks; ++i) {
        representants[i] = i;
    }
    int minSum = 0, noUnitedTreeArches = 0;
    arch unitedTree[MAX_ARCHES];
    int i = 0;
    for (pair<int, pair<int, int>> e : arches) { // iterates through all the "sorted by cost" arches
        ++i;
        int start = e.second.first;
        int end = e.second.second;
        int cost = e.first;
        int startRoot = findRoot(start);
        int endRoot = findRoot(end);
        if (startRoot != endRoot) { // if it unites 2 different trees
            unite(startRoot, endRoot);
            minSum += cost;
            unitedTree[++noUnitedTreeArches].start = start;
            unitedTree[noUnitedTreeArches].end = end;
        }
    }
    fout << minSum << "\n" << noUnitedTreeArches << "\n";
    for (int i = 1; i <= noUnitedTreeArches; ++i) {
        fout << unitedTree[i].start << " " << unitedTree[i].end << "\n";
    }
    return 0;
}