#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#include <deque>
#include <fstream>
#include <algorithm>

using namespace std;

struct Neighbour
{
    int vertex, cost;
};

struct Edge
{
    int left, right, cost;
};

class Graph
{
private:
    static const int MAX_VERTICES = 200000;
    static const int MAX_EDGES = 400000;

    int noVertices;
    int noEdges;

    vector<vector<Neighbour>> neighbours;
    vector<Edge> edges;
    vector<int> parent;         // acest 'parent' e folosit pentru union-find

    int findRoot(int vertex)
    {
        if (parent[vertex] != vertex)
            parent[vertex] = findRoot(parent[vertex]);

        return parent[vertex];
    }

    void mergeConnectedComponents(int vertex1, int vertex2)
    {
        int root1 = findRoot(vertex1);
        int root2 = findRoot(vertex2);

        if (root1 == root2)
            return;

        parent[root1] = root2;
    }

    static int compareEdges(Edge edge1, Edge edge2)
    {
        return edge1.cost < edge2.cost;
    }

public:
    Graph(int noVertices, int noEdges)
        : noVertices(noVertices), noEdges(noEdges),
          neighbours(noVertices + 1),
          parent(noVertices + 1)
    {
        for (int i = 0; i <= noVertices; i++)
            parent[i] = i;
    }

    int getNoVertices()
    {
        return noVertices;
    }

    int getNoEdges()
    {
        return noEdges;
    }

    void addEdgeNeighbours(int vertex1, int vertex2, int cost)
    {
        edges.push_back({vertex1, vertex2, cost});

        neighbours[vertex1].push_back({vertex2, cost});
        neighbours[vertex2].push_back({vertex1, cost});
    }

    void addEdge(int vertex1, int vertex2, int cost)
    {
        edges.push_back({vertex1, vertex2, cost});
    }

    void addNeighbour(int vertex, int neighbour_to_add, int cost)
    {
        neighbours[vertex].push_back({neighbour_to_add, cost});
    }

    void sortAllEdges()
    {
        std::sort(edges.begin(), edges.end(), compareEdges);
    }

    void calculateAPM(int& cost, vector<Edge>& result)
    {
        cost = 0;
        result = vector<Edge> ();

        for (Edge ed : edges)
        {
            if (findRoot(ed.left) == findRoot(ed.right))
                continue;

            cost += ed.cost;
            mergeConnectedComponents(ed.left, ed.right);
            result.push_back(ed);
        }
    }
};



int main()
{
    int N, M;

    ifstream fin ("apm.in");
    fin>> N >> M;
    Graph graph(N, M);

    for (int i=1; i<=M; i++)
    {
        int left, right, cost;
        fin >> left >> right >> cost;

        graph.addEdgeNeighbours(left, right, cost);
    }
    
    fin.close();

    graph.sortAllEdges();

    vector<Edge> result;
    int cost;
    graph.calculateAPM(cost, result);

    ofstream fout("apm.out");
    fout << cost << "\n"
         << result.size() << "\n";

    for (Edge edge : result)
        fout << edge.left << " " << edge.right << "\n";

    fout.close();

    return 0;
}