#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAX 200002
using namespace std;
int n,m,x,y,c,T[MAX];
vector<pair<int, pair<int, int>>> edges;
vector<pair<int, int>> rsp;
/// first                       = costul
/// second.first, second.second = muchiile

ifstream fin("apm.in");
ofstream fout("apm.out");

int get_root(int x){
    int root = x;
    while(T[root] > 0){
        root = T[root];
    }
    /// compresam drumu
    while(x != root){
        int t = T[x];
        T[x] = root;
        x = t;
    }
    return root;
}

bool join(int x, int y){
    int root_x = get_root(x);
    int root_y = get_root(y);
    if(root_x == root_y){
        /// formeaza ciclu
        return false;
    }
    /// facem join
    if(T[root_x] <= T[root_y]){
        /// x are mai multe noduri
        T[root_x] += T[root_y];
        T[root_y] = root_x;
    }else{
        /// y are mai multe noduri
        T[root_y] += T[root_x];
        T[root_x] = root_y;
    }
    return true;
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> x >> y >> c;
        edges.push_back({c, {x,y}});
    }
    sort(edges.begin(), edges.end());

    for(int i = 1; i <= n; i++){
        T[i] = -1;
    }

    int ans = 0;
    for(int i = 0; i < (int) edges.size(); i++){
        int cost = edges[i].first;
        int x = edges[i].second.first;
        int y = edges[i].second.second;

        if(join(x, y)){
            rsp.push_back({x, y});
            ans += cost;
        }
    }
    fout << ans << "\n";
    fout << rsp.size() << "\n";
    for(int i = 0; i < (int) rsp.size(); i++){
        fout << rsp[i].second << " " << rsp[i].first << "\n";
    }
    return 0;
}