#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct node{
    int parent;
    int rank;
};
struct edge {
    int src;
    int dst;
    int wt;
};
vector <node> dsuf;
vector <edge> mst;
bool comparator (edge a, edge b){
    return a.wt < b.wt;
}
int find (int v){
    if (dsuf[v].parent == -1)
        return v;
    dsuf[v].parent = find (dsuf[v].parent);
    return dsuf[v].parent;
}
void union_op(int fromP, int toP){
    //union by rank
    //fromP are higher rank
    if (dsuf[fromP].rank > dsuf[toP].rank)
        dsuf[toP].parent = fromP;
    else
        if (dsuf[fromP].rank < dsuf[toP].rank)
            // toP has higher rank
            dsuf[fromP].parent = toP;
        else{
            // ambele au acelasi rang -> ambii pot fi facuti parinti
            dsuf[fromP].parent = toP;
            dsuf[toP].rank += 1;    //increase rank of parent
        }
}
void Kruskal(vector<edge>& edgeList, int v, int e){
    //sortare dupa weight
    sort(edgeList.begin(), edgeList.end(), comparator);
    int i=0, j=0;
    int fromP, toP;
    //msp o sa aiba v-1 muchii
    while (i<v-1 && j<e){
        fromP = find(edgeList[j].src); // find absolute parent
        toP = find(edgeList[j].dst);
        if (fromP == toP){
            j++;
            continue;
        }
        // union operation
        union_op(fromP, toP); // union for 2 sets;
        mst.push_back(edgeList[j]);
        i++;
    }
}
void printMST (vector<edge>& mst){
    ofstream g ("apm.out");
    int i, sum = 0;
    for (i=0; i<mst.size(); i++){
        sum += mst[i].wt;
    }
    g << sum << endl;
    g << mst.size() << endl;
    for (i=0; i<mst.size(); i++){
        g << mst[i].src << " " << mst[i].dst << endl;
    }
    g.close();
}
int main() {
    int e, v;
    ifstream f ("apm.in");
    f >> v >> e;
    int i;
    dsuf.resize(v);
    for (i=1; i<= v; i++){
        // initializarea setului de date
        dsuf[i].parent = -1;
        dsuf[i].rank = 0;
    }
    vector <edge> edgeList; //for the graph
    edge temp;
    for (i=1; i<=e; i++){
        f >> temp.src >> temp.dst >> temp.wt;
        edgeList.push_back(temp);
    }
    Kruskal(edgeList, v, e);
    printMST(mst);
    return 0;
}