#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

struct edge{
    int u, v, cost;
};

//n - number of nodes
//m - number of edges
int n, m;

//height - array containing the height of each tree in union / find forest
//parent - array containing the parent of each node in the union / find tree
int * height, * parent;

vector<edge> edges;

//a list that sotres the edges in MCST
list<pair<int,int>> solution;
int minimumCost, MCSTedges;

void readEdges(ifstream & in){
    in>>n>>m;

    edges.resize(m);

    int u, v, cost;

    for(int i = 0; i < m; i++){
        in>>u>>v>>cost;
        edges[i].u = u;
        edges[i].v = v;
        edges[i].cost = cost;
    }

}

void initUF(){
    height = new int[n+1];
    parent = new int[n+1];
    for(int i = 0; i <= n; i++){
        height[i] = parent[i] = 0;
    }
}

int reprezUF(int u){
    if(parent[u] == 0)
        return u;
    parent[u] = reprezUF(parent[u]);
    return parent[u];
}

void unionUF(int ru, int rv){
    // int ru = reprezUF(u), rv = reprezUF(v);
    if(height[ru] > height[rv])
        parent[rv] = ru;
    else{
        parent[ru] = rv;
        if(height[ru] == height[rv])
                height[rv]++;
    }
}

int main(){
    ifstream in("apm.in");
    ofstream out("apm.out");
    //read the edges
    readEdges(in);

    //sort edges by cost
    sort(edges.begin(), edges.end(), 
        [](edge const &e1, edge const &e2){
            return e1.cost < e2.cost;
        });

    //initialize union / find structure 
    initUF();

    //traversing edges in order of costs
    int u, v, ru, rv, cost;
    for(auto edge : edges){
        u = edge.u;
        v = edge.v;
        cost = edge.cost;
        ru = reprezUF(u);
        rv = reprezUF(v);
        //if the edge connects 2 components
        if(ru != rv){
            //unite the 2 components
            unionUF(ru, rv);
            MCSTedges++;
            minimumCost += cost;
            solution.push_back(make_pair(u, v));
        }
    }

    out<<minimumCost<<endl<<MCSTedges<<endl;
    for(auto edge : solution)
        out<<edge.first<<' '<<edge.second<<endl;    
}