#include <bits/stdc++.h>
using namespace std;

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

struct edge {
    int node1, node2, cost;
};

int nodes, edges, T[200005], M, TC;
vector <pair <int, int>> MST;
vector <edge> G;

bool cmp (edge X, edge Y) {
    return (X.cost <= Y.cost);
}

int Root (int node) {
    if(T[node] != node)
        T[node] = Root(T[node]);

    return T[node];
}

void read_input () {
    in >> nodes >> edges;
    for (int i = 1 ; i <= edges; ++ i) {
        edge X;
        in >> X.node1 >> X.node2 >> X.cost;
        G.push_back(X);
    }
}

void JOIN (int node1, int node2){
    T[node2] = node1;
}

void Solve () {
     sort (G.begin(), G.end(), cmp);

     for (int i = 1 ; i <= nodes ; ++ i) {
        T[i] = i;
     }

     int nr = nodes;

     for (auto &it: G){
            edge crt = it;
            int rootX = Root(crt.node1);
            int rootY = Root(crt.node2);

            if (rootX != rootY) {
                    JOIN (rootX, rootY);
                    -- nr;
                    TC += crt.cost;
                    ++ M;
                    MST.push_back(make_pair(crt.node1, crt.node2));
            }

            if (nr == 0) {
                break;
            }
        }
}

void write () {
    out << TC << '\n' << M << '\n';

    for(auto &it: MST){
        out << it.first << " "<<it.second << '\n';
    }


}

int main() {
    read_input ();
    Solve ();
    write ();

    return 0;
}