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

bool sortKruskal( const vector<int> &v1, const vector<int> &v2){
    return v1[2] < v2[2];
}

class Graph{
    int Nodes, nrEdges;
    vector< vector<int> > edgeList;
    // Union-Find elements for Kruskal
    vector<int> Heights, Fathers;

public:
    int getNodes() { return this->Nodes;}
    vector< vector<int> > getEdgeList() { return this->edgeList; }

    void readAdjancencyList();

    // Union-Find functions
    void Init(int);
    int Find(int);
    void Union(int,int);

    // Kruskal
    void Kruskal();
};

void Graph::readAdjancencyList() {
    ifstream fin("apm.in");
    fin >> this->Nodes;
    fin >> this->nrEdges;

    this->Heights.resize(this->Nodes + 1);
    this->Fathers.resize(this->Nodes + 1);

    for(int i = 0; i < this->nrEdges; i++){
        int x, y, pondere;
        fin >> x >> y >> pondere;
        edgeList.push_back(vector<int>{x,y,pondere});
    }

    fin.close();
}

void Graph::Init(int Node) {
    this->Heights[Node] = 0;
    this->Fathers[Node] = 0;
}

int Graph::Find(int Node) {
    if(Fathers[Node] == 0)
        return Node;
    Fathers[Node] = Find(Fathers[Node]);
    return Fathers[Node];
}

void Graph::Union(int Node1, int Node2) {
    int Root1 = Find(Node1), Root2 = Find(Node2);
    if( Heights[Root1] < Heights[Root2]){
        Fathers[Root1] = Root2;
    } else if( Heights[Root1] > Heights[Root2]) {
        Fathers[Root2] = Root1;
    } else {
        Fathers[Root1] = Root2;
        Heights[Root2]++;
    }
}

void Graph::Kruskal() {
    ofstream fout("apm.out");
    // Sort the vector of edges
    sort(this->edgeList.begin(), this->edgeList.end(), sortKruskal);

    for(int i = 1; i <= this->Nodes; i++)
        Init(i);

    vector<pair<int,int>> APCM;
    int nrArbore = 0;
    int SumAPCM = 0;

    for(int i = 0; i < this->edgeList.size(); i++){
        int NodeX = edgeList[i][0], NodeY = edgeList[i][1];

        // If the two nodes are not in the same connected component
        if(this->Find(NodeX) != this->Find(NodeY)){
            // Add the edge to the APCM
            APCM.push_back(make_pair(NodeX,NodeY));
            SumAPCM += edgeList[i][2];

            this->Union(NodeX, NodeY);
            nrArbore++;
            if(nrArbore == this->Nodes - 1)
                break;
        }
    }

    fout << SumAPCM << endl;
    fout << APCM.size() << endl;
    for(int i = 0; i < APCM.size(); i++)
        fout << APCM[i].first << " " << APCM[i].second << endl;
}

int main() {
    Graph graf;
    graf.readAdjancencyList();
    graf.Kruskal();
    return 0;
}