#include <algorithm>
#include <fstream>
#include <tuple>
#include <vector>
using namespace std;

typedef tuple<int, int, int> edge_t;

struct UF {
    vector<int> set;
    
    UF(const int n) : set(n) {
        iota(set.begin(), set.end(), 0);
    }
    
    int find(int x) {
        for (int t = x; set[x] != x; t = x) {
            x = set[t];
            set[t] = set[set[t]];
        }
        
        return x;
    }
    
    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        
        if (x == y) return;
        set[y] = x;
    }
};

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    
    int n, m; fin >> n >> m;
    vector<edge_t> edges;
    
    for (; m; --m) {
        int x, y, c;
        fin >> x >> y >> c;
        edges.push_back(make_tuple(x, y, c));
    }
    
    sort(edges.begin(), edges.end(),
        [] (const edge_t& a, const edge_t& b) { return get<2>(a) < get<2>(b); });
    
    vector<edge_t> apm;
    UF uf(n);
    long long cost = 0;
    
    for (auto& edge : edges) {
        int u = get<0>(edge) - 1, v = get<1>(edge) - 1;
        
        if (uf.find(u) != uf.find(v)) {
            apm.push_back(make_tuple(u+1, v+1, 0));
            cost += get<2>(edge);
            
            if (apm.size() == n-1) break;
            uf.merge(u, v);
        }
    }
    
    fout << cost << '\n' << n-1 << '\n';
    for (auto& edge : apm)
        fout << get<0>(edge) << ' ' << get<1>(edge) << '\n';
    
    return 0;
}