#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

struct Edge{
    int start;
    int finish;
    int cost;
};

bool comp(Edge A, Edge B) {
    return A.cost < B.cost;
}

int group(int n, vector<int> & groups) {
    if(groups[n] == n)
        return n;

    groups[n] = group(groups[n], groups);
    return groups[n];
}

void unite(int a, int b, vector<int> & groups) {
    groups[ group(a, groups) ] = group(b, groups);
}

int main() {
    int n, m;
    fin >> n >> m;
    vector<Edge> edges;
    vector<int> groups(n + 5);

    for(int i = 1; i <= m; i++) {
        Edge crtEdge;
        fin >> crtEdge.start >> crtEdge.finish >> crtEdge.cost;
        edges.push_back(crtEdge);
    }

    for(int i = 1; i <= n; i++) {
        groups[i] = i;
    }

    sort(edges.begin(), edges.end(), comp);

    int totalCost = 0;
    vector<Edge> usedEdges;
    for(auto edge: edges) {
        if( group(edge.start, groups) != group(edge.finish, groups) ) {
            unite(edge.start, edge.finish, groups);
            totalCost += edge.cost;
            usedEdges.push_back(edge);
        }
    }

    fout << totalCost << "\n" << n - 1 << "\n";
    for(auto edge: usedEdges) {
        fout << edge.start << " " << edge.finish << "\n";
    }

    return 0;
}