#include <fstream>
#include <algorithm>
#include <vector>
std::ifstream fin("apm.in");
std::ofstream fout("apm.out");
#define N 100002
std::vector<std::vector<std::pair<int, int>>> V;
std::vector<std::pair<int, std::pair<int, int>>> edges;
std::vector<std::pair<int, int>> res;
int n, m, frv[N], size[N];
int find(int x){
    int root = x;
    while(root != frv[root]){
        root = frv[root];
    }
    while(x != root){
        int aux = frv[x];
        frv[x] = root;
        x = aux;
    }
    return root;
}

void unite(int u, int v){
    if(size[u] > size[v]){
        frv[v] = u;
        size[u] += size[v];
    }
    else{
        frv[u] = v;
        size[v] += size[u];
    }
}

int kruskal(){
    int total_cost = 0;
    for(int i = 0; i < m; i++){
        int x = edges[i].second.first, y = edges[i].second.second;
        
        if(find(x) != find(y)){
            unite(find(x), find(y));
            res.push_back({x, y});
            total_cost += edges[i].first;
        }
    }
    return total_cost;
}
int main(){
    fin >> n >> m;
    for(int i = 1; i <= n; i++){
        frv[i] = i;
        size[i] = 1;
    }
    V = std::vector<std::vector<std::pair<int, int>>> (n + 1);
    //edges = std::vector<std::pair<int, std::pair<int, int>>> (m + 1);
    int x, y, cost;
    for(int i = 1; i <= m; i++){
        fin >> x >> y >> cost;
        V[x].push_back({y, cost});
        V[y].push_back({x, cost});
        edges.push_back({cost, {x, y}});
    }
    std::sort(edges.begin(), edges.end());
    fout << kruskal() << "\n";
    fout << res.size() << "\n";
    for(std::pair<int, int> it : res){
        fout << it.first << " " << it.second << "\n";
    }
}