#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];
int dist[200005];
bool comp( const kruskal_state &a, const kruskal_state &b){
    if(a.to_cost > b.to_cost)
        return false;
    return true;


}
long long tot_cost = 0;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<kruskal_state> result_print;
int 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[b] = 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 <<" "<< result_print[i].to_cost<<"\n";

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