#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 200001
using namespace std;

void get_data (vector< pair <pair <int, int>, int > > &edges, int &n_nodes){
    ifstream fin ("apm.in");
    int n_edges;
    fin >> n_nodes >> n_edges;
    for (int i = 1; i <= n_edges; i++){
        int node_1, node_2, value;
        fin >> node_1 >> node_2 >> value;
        edges.push_back (make_pair (make_pair (node_1, node_2), value));
    }
}

bool cmp (pair <pair <int, int>, int > x, pair <pair < int, int>, int > y){
   return x.second < y.second;
}

int find_root (int root_1, int ind_node[nmax]){
    if (ind_node[root_1] < 0)
        return root_1;
    return find_root (ind_node[root_1], ind_node);
}

void reunion (int node_1, int node_2, int ind_node[nmax]){
    if (ind_node[node_1] < ind_node[node_2]){
        ind_node[node_1] += ind_node[node_2];
        ind_node[node_2] = node_1;
    }
    else{
        ind_node[node_2] += ind_node[node_1];
        ind_node[node_1] = node_2;
    }
}

int apm (vector <pair <pair <int, int>, int > > &edges, int &n_nodes, vector <pair <int, int> > &apm_edges, int &apm_nodes){
    int apm_value = 0;
    int ind_node[nmax];
    for (int i = 1; i <= n_nodes; i++)
        ind_node[i] = -1;
    sort (edges.begin(), edges.end(), cmp);
    apm_nodes = 0;
    for (auto x : edges){
        int root_1 = find_root (x.first.first, ind_node);
        int root_2 = find_root (x.first.second, ind_node);
        if (root_1 != root_2){
            reunion (root_1, root_2, ind_node);
            apm_nodes ++;
            apm_value += x.second;
            apm_edges.push_back (make_pair (x.first.first, x.first.second));
        }
        if (apm_nodes == n_nodes - 1)
            break;
    }
    return apm_value;
}

void print_data (vector <pair <pair <int, int>, int > > &edges, int &n_nodes){
    ofstream fout ("apm.out");
    int apm_nodes;
    vector <pair <int, int> > apm_edges;
    fout << apm (edges, n_nodes, apm_edges, apm_nodes) << "\n" << apm_nodes + 1 << "\n";
    for (auto x : apm_edges)
        fout << x.first << " " << x.second << "\n";
}


int main(){
    int n_nodes;
    vector <pair <pair <int, int>, int > > edges;
    get_data (edges, n_nodes);
    print_data (edges, n_nodes);
    return 0;
}