#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct vertex {
    int edge;
    int weight;
};
struct complete_vertex {
    int edgeA;
    int edgeB;
    int weight;
    bool operator<(const complete_vertex& foreign) const {
        return this->weight > foreign.weight;
    }
};

int E,V;
vector<int> T;

int getRoot(int node) {
    int _node = node;
    while (T[node] > 0) {
        node = T[node];
    }
    while(_node != node) {
        const int aux = T[_node];
        T[_node] = node;
        _node = aux;
    }
    return node;
}

void join(int edgeA, int edgeB){
    const int rootA = getRoot(edgeA);
    const int rootB = getRoot(edgeB);
    if (rootA > rootB) {
        T[rootB] += T[rootA];
        T[rootA] = rootB;
    } else {
        T[rootA] += T[rootB];
        T[rootB] = rootA;
    }

}

int main() {
    fin >> E >> V;
    T.assign(E+1, -1);
    long long ans_weight = 0;
    vector<forward_list<vertex>> G(E+1);
    priority_queue<complete_vertex> pq;
    queue<vertex> ans;
    for (int i = 1; i <= V; i++) {
        int edgeA, edgeB, value;
        fin >> edgeA >> edgeB >> value;
        G[edgeA].push_front({edgeB, value});
        pq.push({edgeA, edgeB, value});
    }
    while(!pq.empty()) {
        const complete_vertex curr = pq.top();
        const int rootA = getRoot(curr.edgeA);
        const int rootB = getRoot(curr.edgeB);
        if (rootA == rootB);
        else {
            join(curr.edgeA, curr.edgeB);
            ans_weight += curr.weight;
            ans.push({curr.edgeA,curr.edgeB});
        }
        pq.pop();
    }
    fout << ans_weight << '\n';
    fout << ans.size() << '\n';
    while (!ans.empty()) {
        fout << ans.front().edge << ' ' << ans.front().weight << '\n';
        ans.pop();
    }

    return 0;
}