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

using namespace std;

struct Neighbour
{
    int vertex, cost;
};



// Possible edges to add in the APM
struct APMEdge
{
    int apmVertex, outsideVertex, cost;
};


class Graph
{
private:
    struct CompareCost
    {
        bool operator()(const APMEdge &a, const APMEdge &b) const
        {
            return a.cost > b.cost;
        }
    };

    static const int MAX_VERTICES = 200000;
    static const int MAX_EDGES = 400000;

    int noVertices;
    int noEdges;

    vector<vector<Neighbour>> neighbours;

    vector<int> parent;
    priority_queue<APMEdge, vector<APMEdge>, CompareCost> costToAPM;
    // cost to the APM

public:
    Graph(int noVertices, int noEdges)
        : noVertices(noVertices), noEdges(noEdges),
          neighbours(noVertices + 1),
          parent(noVertices + 1, -1)
    {
    }

    int getNoVertices()
    {
        return noVertices;
    }

    int getNoEdges()
    {
        return noEdges;
    }

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

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

    int calculateAPM()
    {
        int costToReturn = 0;

        parent[1] = 0;

        for (Neighbour neigh : neighbours[1])
            costToAPM.push(APMEdge{1, neigh.vertex, neigh.cost});


        // !!!! In cazul de fata, neigh.vertex tine minte nodul din care plecam
        // Adica parcurgand nodurile din afara APM-ului, dorim sa tinem minte costul minim catre
        // un nod din interiorul APM-ului

        while (!costToAPM.empty())
        {
            APMEdge currEdge = costToAPM.top();
            costToAPM.pop();

            if (parent[currEdge.outsideVertex] != -1)
            {
                continue;
            }

            costToReturn = costToReturn + currEdge.cost;

            parent[currEdge.outsideVertex] = currEdge.apmVertex;
            

            for (Neighbour neigh : neighbours[currEdge.outsideVertex])
                if (parent[neigh.vertex] == -1)
                    costToAPM.push({currEdge.outsideVertex, neigh.vertex, neigh.cost});
        }

        return costToReturn;
    }

    vector<int>& getParentArray()
    {
        return parent;
    }
};



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.addNeighbours(left, right, cost);
    }
    
    fin.close();


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

    result = graph.getParentArray();

    ofstream fout("apm.out");
    fout << cost << "\n"
         << N-1 << "\n";

    for (int i=1; i <= N; i++)
        if (result[i] != 0)
            fout << i << " " << result[i] << "\n";

    fout.close();

    return 0;
}