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

using namespace std;

struct Neighbour
{
    int vertex, 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<int> parent;
    vector<Neighbour> costToAPM;
    // cost to the APM

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

    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;
        costToAPM[1].cost = -INT_MAX;
        costToAPM[1].vertex = 1;


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



        // !!!! 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

        for (int i=2; i <= noVertices; i++)
        {
            int curr_vertex;
            Neighbour curr_neighbour;
            curr_neighbour.cost = INT_MAX;
            
            for (int i=1; i <= noVertices; i++)
                if (costToAPM[i].cost != -INT_MAX && costToAPM[i].cost < curr_neighbour.cost)
                {
                    curr_vertex = i;
                    curr_neighbour = costToAPM[i];
                }

            costToReturn = costToReturn + costToAPM[curr_vertex].cost;

            parent[curr_vertex] = curr_neighbour.vertex;
            costToAPM[curr_vertex].cost = -INT_MAX;
            costToAPM[curr_vertex].vertex = curr_vertex;
            

            for (Neighbour neigh : neighbours[curr_vertex])
                if (costToAPM[neigh.vertex].cost != -INT_MAX && neigh.cost < costToAPM[neigh.vertex].cost)
                    {
                        costToAPM[neigh.vertex].cost = neigh.cost;
                        costToAPM[neigh.vertex].vertex = curr_vertex;
                    }
        }

        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;
}