#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

bool customSort(const pair<pair<int,int>,int> &a, const pair<pair<int,int>,int> &b) {
    return a.second < b.second;
}

int getRep(int a, vector<int> &rep) {

    if(rep[a] == 0)
        return a;
    
    return rep[a] = getRep(rep[a], rep);

}

void combine(int a, int b, vector<int> &rep, vector<int> &size) {
    if(a == b)
        return ;

    if(size[a] <= size[b]) {
        rep[b] = a;
        size[a] += size[b];
    }
    else {
        rep[a] = b;
        size[b] += size[a];
    }
}

int main() {

    int noNodes, noEdges, sum = 0, cnt = 0;
    fin >> noNodes >> noEdges;
    vector<pair<pair<int,int>,int>> graph;
    vector<int> rep(noNodes+1, 0);
    vector<int> size(noNodes+1, 1);
    vector<pair<int,int>> edges;

    for(int i=1; i<=noEdges; i++) {
        int firstNode, secondNode, weight;
        fin >> firstNode >> secondNode >> weight;
        graph.push_back({{firstNode, secondNode}, weight});

    }

    sort(graph.begin(), graph.end(), customSort);

    for(auto e : graph) {

        int newA = getRep(e.first.first, rep);
        int newB = getRep(e.first.second, rep);

        if(newA != newB) {
            edges.push_back({e.first.first, e.first.second});
            cnt++;
            sum+= e.second;
        }

        combine(newA, newB, rep, size);
    }

    fout << sum << '\n' << cnt << '\n';

    for(auto e : edges) {
        fout << e.first << ' ' << e.second << '\n';
    }

    return 0;
}