#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>

// QUESTION 1
struct edge {
    // extremities
    int from;
    int to;
    // cost of the edge ( set it to float or double if you work with floating point numbers )
    int cost;

    // overload operator< ( QUESTION 4 )
    bool operator<(edge e) {
        return cost < e.cost;
    }
};

// QUESTION 2
struct ACM_DATA {
    // number of vertices and edges
    int V;
    int E;
    // vector of edges
    // ( can use a simple array, but it's harder to deal with its dimension, so we use a dynamic std::vector )
    std::vector<edge> edges;
};

// QUESTION 5
// sort the edges of a graph by their cost, using selection sort
// pass by reference to avoid making any copies
void sortEdges_selection(ACM_DATA& g) {
    // move the boundary of the unsorted vector one by one
    for (int i = 0; i < g.E - 1; i++) {
        // consider the minimum element to be element at index i
        int min_idx = i;
        // find the minimum element in the unsorted vector
        for (int j = i + 1; j < g.E; j++) {
            // if we found a cost that's smaller
            if (g.edges[j].cost < g.edges[min_idx].cost) {
                // set min_idx to that index
                min_idx = j;
            }
        }
        // swap the minimum cost edge found with the current edge
        edge aux = g.edges[i];
        g.edges[i] = g.edges[min_idx];
        g.edges[min_idx] = aux;
    }
}

// QUESTION 8
// sort the edges of a graph by their cost, using quick sort
// pass by reference to avoid making any copies
void sortEdges_quick(ACM_DATA& g) {
    std::sort(g.edges.begin(), g.edges.end());
}

// QUESTION 6
// ACM_Solution structure
struct ACM_Solution {
    // total cost of the minimum spanning tree ( change to float / double if needed )
    // set it to initially be 0
    int MST_cost = 0;
    // MST's vector of edges
    std::vector<edge> MST_edges;
};

// kruskal's algorithm
ACM_Solution Kruskal(ACM_DATA g) {
    // initialize the solution
    ACM_Solution MST;

    // first, sort the edges of the graph in ascending order
    // sortEdges_selection(g);
    sortEdges_quick(g);

    // vector of parents for each vertex
    // need it to detect if we create any cycle
    // first element will be 0, we ignore it, since we start indexing the vertices from 1
    std::vector<int> P = {0};

    // initially, set each vertex to be its own parent
    for (int i = 1; i <= g.V; i++) {
        P.push_back(i);
    }

    // go through all of the edges
    // and terminate early if we have |V| - 1 edges in the MST
    // ( cast the g.V to unsigned int when comparing it to the size of the mst's edge vector to avoid warnings from the compiler )
    for (int i = 0; (i < g.E) && (MST.MST_edges.size() <= (unsigned int) g.V - 1); i++) {
        // if the edge does not form a cycle
        if (P[g.edges[i].from] != P[g.edges[i].to]) {
            // add the edge to the MST and increase the total cost with the edge's cost
            MST.MST_edges.push_back(g.edges[i]);
			MST.MST_cost += g.edges[i].cost;
			// and merge the two components
			int from = P[g.edges[i].from];
			int to = P[g.edges[i].to];
			for (int j = 1 ; j <= g.V ; ++j) {
				if(P[j] == to) {
					P[j] = from;
				}
			}
		}
    }
    // finally, return the solution
    return MST;
}

int main() {
    // declare an ACM_DATA structure ( QUESTION 3 )
    ACM_DATA graph;

    // open the file and read from stdin
    freopen("apm.in", "r", stdin);

    // read the number of vertices and edges
    // also check that we have got two inputs with assert
    // remove the assert and only keep the scanf if it bothers you, but it's good to have some input checking
    assert(scanf("%d %d", &graph.V, &graph.E) == 2);

    // read each edge with
    // declare cost as double if working with floating point numbers
    int from, to, cost;
    for (int i = 0; i < graph.E; i++) {
        // read the edge's data
        assert(scanf("%d %d %d", &from, &to, &cost));
        // create an edge and push it into the graph's edge vector
        graph.edges.push_back(edge{from, to, cost});
    }

    // get the MST
    ACM_Solution MST = Kruskal(graph);

    freopen("apm.out", "w", stdout);

    // print it
    // first the cost
    std::cout << MST.MST_cost << '\n' << MST.MST_edges.size() << '\n';
    // now the edges
    for (size_t i = 0; i < MST.MST_edges.size(); i++) {
        std::cout << MST.MST_edges[i].to << ' ' << MST.MST_edges[i].from << '\n';//<< ' ' << MST.MST_edges[i].cost << '\n';
    }

    return 0;
}