#include <cassert>
#ifdef DEBUG
    #include <iostream>
#endif
#include <fstream>
#include <stdlib.h>

using namespace std;

typedef struct _node {
    int number;
    int parent;
    bool visited;
} Node;

typedef struct _edge {
    int fromNode;
    int toNode;
    long int weight;
    bool isTaken;
    bool visited;
} Edge;

const int NODE_NOT_VISITED = -1;
const int NO_PARENT = -2;
const int NO_MORE_NODES = -1;

int numberOfNodes;
long int numberOfEdges;
Node *nodes;
Edge *edges;

int firstNodeToVisit(void) {
    for (int i = 0; i < numberOfNodes; ++i) {
        if (nodes[i].visited == false) {
            return i;
        }
    }
    return NO_MORE_NODES;
}

int findEdge(int first, int second) {
    for (long int i = 0; i < numberOfEdges; ++i) {
        if (((edges[i].fromNode == first && edges[i].toNode == second))
          || (edges[i].fromNode == second && edges[i].toNode == first)) {
            return i;
        }
    }
    assert(false);
    return -1;
}

int main(void) {
    ifstream fin("input.txt"); assert(fin);
    fin >> numberOfNodes;
    fin >> numberOfEdges;
    nodes = (Node *) malloc(sizeof(Node) * numberOfNodes);
    assert(nodes != NULL);
    for (int i = 0; i < numberOfNodes; ++i) {
        nodes[i].number = i + 1;
        nodes[i].parent = NODE_NOT_VISITED;
        nodes[i].visited = false;
    }
    edges = (Edge *) malloc(sizeof(Edge) * numberOfEdges);
    assert(edges != NULL);
    for (long int i = 0; i < numberOfEdges; ++i) {
        fin >> edges[i].fromNode;
        fin >> edges[i].toNode;
        fin >> edges[i].weight;
        edges[i].fromNode -= 1;
        edges[i].toNode -= 1;
        edges[i].isTaken = false;
        edges[i].visited = false;
    }
    fin.close();
#ifdef DEBUG
    cout << "Nodi e archi:" << endl;
    for (int i = 0; i < numberOfNodes; ++i) {
        cout << (nodes[i].number) << " " << (nodes[i].parent + 1) << endl;
    }
    for (long int i = 0; i < numberOfEdges; ++i) {
        cout << (edges[i].fromNode + 1) << " " << (edges[i].toNode + 1) << " " << edges[i].weight << " " << edges[i].isTaken << endl;
    }
#endif
    int minCost = 0;
    int currentNode = firstNodeToVisit();
    while (currentNode != NO_MORE_NODES) {
    #ifdef DEBUG
        cout << "Corrente: " << (currentNode + 1) << endl;
    #endif
        if (nodes[currentNode].parent == NODE_NOT_VISITED) {
            nodes[currentNode].parent = NO_PARENT;
        }
        nodes[currentNode].visited = true;
        for (long int i = 0; i < numberOfEdges; ++i) {
            if (edges[i].fromNode == currentNode || edges[i].toNode == currentNode) {
                int childIndex = (edges[i].fromNode == currentNode ? edges[i].toNode : edges[i].fromNode);
                #ifdef DEBUG
                    cout << "Arco corrente: da " << (currentNode + 1) << " a " << (childIndex + 1) << endl;
                #endif
                if (edges[i].visited) {
                    #ifdef DEBUG
                        cout << "Già visto" << endl;
                    #endif
                    continue;
                }
                edges[i].visited = true;
                if (nodes[childIndex].parent == NO_PARENT || nodes[childIndex].parent == NODE_NOT_VISITED) {
                    #ifdef DEBUG
                        cout << "Non visitato o collegato" << endl;
                    #endif
                    nodes[childIndex].parent = currentNode;
                    #ifdef DEBUG
                        cout << "New parent: " << (nodes[childIndex].parent + 1) << endl;
                    #endif
                    edges[i].isTaken = true;
                } else {
                    #ifdef DEBUG
                        cout << "Ho già un cammino - trova " << childIndex << " " << (nodes[childIndex].parent + 1) << endl;
                    #endif
                    long int oldEdge = findEdge(childIndex, nodes[childIndex].parent);
                    long long int existingWeight = edges[oldEdge].weight;
                    long long int newWeight = edges[i].weight;
                    int expNode = currentNode;
                    while (expNode != nodes[childIndex].parent) {
                        long int expEdge = findEdge(expNode, nodes[expNode].parent);
                        existingWeight += edges[expEdge].weight;
                        #ifdef DEBUG
                            cout << "Nodi " << (expNode + 1) << "-" << (nodes[expNode].parent + 1) << ", costo edge: " << edges[expEdge].weight << endl;
                        #endif
                        expNode = nodes[expNode].parent;
                    }
                    #ifdef DEBUG
                        cout << "Costo vecchio: " << existingWeight << ", costo nuovo: " << newWeight << endl;
                    #endif
                    if (existingWeight > newWeight) {
                        #ifdef DEBUG
                            cout << "Sostituisco!" << endl;
                        #endif
                        nodes[childIndex].parent = currentNode;
                        edges[oldEdge].isTaken = false;
                        edges[i].isTaken = true;
                    }
                }
            }
        }
        currentNode = firstNodeToVisit();
    }
#ifdef DEBUG
    cout << "Nodi e archi:" << endl;
    for (int i = 0; i < numberOfNodes; ++i) {
        cout << (nodes[i].number) << " " << (nodes[i].parent + 1) << endl;
    }
    for (long int i = 0; i < numberOfEdges; ++i) {
        cout << (edges[i].fromNode + 1) << " " << (edges[i].toNode + 1) << " " << edges[i].weight << " " << edges[i].isTaken << endl;
    }
#endif
    ofstream fout("output.txt"); assert(fout);
    minCost = 0;
    for (long int i = 0; i < numberOfEdges; ++i) {
        if (edges[i].isTaken) {
            minCost += edges[i].weight;
        }
    }
    fout << minCost << endl;
    for (long int i = 0; i < numberOfEdges; ++i) {
        if (edges[i].isTaken) {
            fout << (edges[i].fromNode + 1) << " " << (edges[i].toNode + 1) << endl;
        }
    }
    fout.close();
    free(nodes);
    free(edges);
    return 0;
}