#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct kruskal_state{
    int from_node;
    int to_node;
    int to_cost;

};
const int inf = 0x3f3f3f3f;
vector<kruskal_state> initial_vector;
int root[200005];
long long dist[200005];
bool comp( const kruskal_state &a, const kruskal_state &b){
    if(a.to_cost > b.to_cost)
        return false;
    else if(a.to_cost == b.to_cost){
        if(a.from_node > b.from_node)
            return false;
        return true;

    }

    return true;


}
long long tot_cost = 0;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<kruskal_state> result_print;
long long lungime[200005];

int get_root(int node){
    if(root[node] != node){
        int ans = get_root(root[node]);
        root[node] = ans;

    }
    return root[node];
}

void set_root(int a, int b){
    root[get_root(b)] = get_root(a);
    lungime[a] += lungime[b];
}

void kruskal(){

    for(int i = 0; i < initial_vector.size(); i++){
        int first_root = get_root(initial_vector[i].from_node);
        int second_root = get_root(initial_vector[i].to_node);

        if(first_root != second_root){

            if(lungime[first_root] > lungime[second_root]){
                set_root(first_root, second_root);

            }
            else
                set_root(second_root, first_root);
            result_print.push_back(initial_vector[i]);
            tot_cost += initial_vector[i].to_cost;

        }

    }
}
int main()
{
    int n, m;
    fin>>n>>m;
    for(int i = 1; i <= n; i++){
        root[i] = i;
        lungime[i] = 1;
    }

    for(int i = 0; i < m; i++){
        int from_node, to_node, to_cost;
        fin>>from_node>>to_node>>to_cost;
        initial_vector.push_back({from_node, to_node, to_cost});
    }

    sort(initial_vector.begin(), initial_vector.end(), comp);

    kruskal();
    fout<< tot_cost<<"\n";
    fout<<result_print.size()<<"\n";
    for(int i = 0; i < result_print.size(); i++){
        fout<<result_print[i].from_node<<" "<< result_print[i].to_node<<"\n";

    }
    fin.close();
    fout.close();
    return 0;
}