#include <iostream>
#include <algorithm>
#include <fstream>
#include <set>
using namespace std;
 
ifstream fin("apm.in");
ofstream fout("apm.out");
 
const int MAX_PEAKS = 200005;
const int MAX_ARCHES = 400005;

int noPeaks, noArches, representants[MAX_PEAKS];
set<pair<int, pair<int, int>>> arches;
pair<int, int> unitedTree[MAX_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;
    for (pair<int, pair<int, int>> e : arches) {
        int startRoot = findRoot(e.second.first);
        int endRoot = findRoot(e.second.second);
        if (startRoot != endRoot) {
            unite(startRoot, endRoot);
            minSum += e.first;
            unitedTree[++noUnitedTreeArches].first = e.second.first;
            unitedTree[noUnitedTreeArches].second = e.second.second;
        }
    }
    fout << minSum << "\n" << noUnitedTreeArches << "\n";
    for (int i = 1; i <= noUnitedTreeArches; ++i) {
        fout << unitedTree[i].first << " " << unitedTree[i].second << "\n";
    }
    return 0;
}