#include <bits/stdc++.h>

using namespace std;

#define inFile "apm.in"
#define outFile "apm.out"

FILE *in  = fopen(inFile, "r");
FILE *out = fopen(outFile, "w");

#define maxSize 1000002
#define inf 0x3f3f3f3f

int comParent[maxSize], comSize[maxSize];
int findParent(int node) {
    while (node != comParent[node]) node = comParent[node];
    return node;
}


bool connectNodes(int nodeA, int nodeB) {
    nodeA = findParent( nodeA );
    nodeB = findParent( nodeB );

    if (nodeA == nodeB) return false;

    if (comSize[nodeA] < comSize[nodeB]) swap(nodeA, nodeB);
    comParent[nodeB] = nodeA; comSize[nodeA] += comSize[nodeB];
    return true;
}

struct type {
    int nodeA, nodeB, weight;
    bool operator <(const type& other) {
        return weight < other.weight;
    }
};
vector <type> edges;
vector <pair<int , int>> toShow;

int main( ) {
    int numNodes, numEdges; fscanf(in, "%d %d", &numNodes, &numEdges);
    for (int i = 1; i <= numNodes; ++i) {
        comSize[i] = 1;
        comParent[i] = i;
    }

    edges.reserve(numEdges + 1);
    type current;
    for (int i = 0; i < numEdges; ++i) {
        fscanf(in, "%d %d %d", &current.nodeA, &current.nodeB, &current.weight);
        edges.emplace_back( current );
    }

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

    int minCost = 0;
    for (auto curEdge : edges) {
        if (connectNodes(curEdge.nodeA, curEdge.nodeB)) {
            minCost += curEdge.weight;
            toShow.push_back({curEdge.nodeA, curEdge.nodeB});
        }
    }

    fprintf(out, "%d\n", minCost);
    fprintf(out, "%d\n", toShow.size( ));
    for (auto curEdge : toShow) fprintf(out, "%d %d\n", curEdge.first, curEdge.second);
    return 0;
}