#include <iostream>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip>
#include <utility>
#include <fstream>
#include <bitset>
#include <cassert>

using namespace std;
const string InputFile = "apm.in";
const string OutputFile = "apm.out";
const int INF = 0x7fffffff;

class Edge {
public:
    Edge(int dest, int cost) : destination(dest), cost(cost) {
    }

    Edge() : destination(-1), cost(-1) {
    }

    ~Edge() {
    }
    
    int get_dest() const { 
        return destination;
    }
    
    int get_cost() const { 
        return cost;
    }
    
    void set_cost(int cost) {
        this -> cost = cost;
    }
    
    void set_dest(int dest) { 
        this -> destination = dest;
    }

private:
    int destination, cost;
};

auto comparator = [](const Edge& a, const Edge& b) { return a.get_cost() > b.get_cost(); };
typedef vector< vector<Edge> > Graph;
typedef priority_queue<Edge, vector<Edge>, decltype(comparator)> Heap;

istream& operator >> (istream& stream, Graph& graph) {
    int N, M;
    stream >> N >> M;

    graph.resize(N+1);
    for (int i = 0; i < M; ++i) {
        int src, dst, cost;
        stream >> src >> dst >> cost;
        graph[src].push_back(Edge(dst, cost));
        graph[dst].push_back(Edge(src, cost));
    }
    return stream;
}

ostream& operator << (ostream& stream, Graph& graph) {
    for(int nod = 1; nod < static_cast<int>(graph.size()); ++nod) {
        stream << "Nodul " << nod << " : ";
        for (auto neighbour : graph[nod]) {
            stream << "(" << neighbour.get_dest() << ", " << neighbour.get_cost() << ") ";
        }
        stream << '\n';
    }
    return stream;
}

ostream& operator << (ostream& stream, std::vector<pair<int, Edge>>& apm) {
    stream << apm.size() << '\n';
    for (auto edge : apm)
        stream << edge.first << " " << edge.second.get_dest() << "\n";
    return stream;
}

//Prim's algorithm
int APM_with_Prim(Graph& graph, int source, vector<pair<int,Edge> >& apm) {
    int apm_cost = 0;
    vector<int> costs(graph.size(), INF);
    vector<int> parent(graph.size());
    vector<bool> verified(graph.size());
    Heap pq(comparator);

    assert( 0 < source && source < static_cast<int>(graph.size()) );
    verified[source] = 1;
    costs[source] = 0;
    parent[source] = -1;

    for (auto neighbour : graph[source] ) {
       costs[neighbour.get_dest()] = neighbour.get_cost();
       pq.push(neighbour);
       parent[neighbour.get_dest()] = source;
    }

    while (!pq.empty()) {
        Edge e = pq.top();
        pq.pop();

        int nod = e.get_dest();
        int cost = e.get_cost();
        int dad = parent[nod];

        if (verified[nod])
            continue;

        verified[nod] = 1;
        for (auto neighbour : graph[nod])
            if (costs[neighbour.get_dest()] > neighbour.get_cost() ) {
                costs[neighbour.get_dest()] = neighbour.get_cost();
                pq.push(neighbour);
                parent[neighbour.get_dest()] = nod;
            }
        apm_cost += cost;
        apm.push_back(make_pair(dad, e));
    } 
    return apm_cost;
}

//Kruskal's algorithm

int main(int argc, char* argv[]) {
    ifstream fin(InputFile);
    ofstream fout(OutputFile);
    Graph graph;
    vector<pair<int,Edge> > apm;
    int apm_cost;

    fin >> graph;
    apm_cost = APM_with_Prim(graph, 1, apm);

    //cout << graph;
    fout << apm_cost << '\n' << apm;
    return 0;
}