#include <vector>
#include <fstream>
#include <algorithm>

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


class DSU{
private:
    std::vector<int>rank, parent;
    int V;
public:
    DSU(int n) {
        V = n+1;
        rank.resize(V);
        parent.resize(V);
        for(int i=1;i<V;++i) {
            rank[i] = 1;
            parent[i] = i;
        }
    }

    int find(int i) {
        return (parent[i] == i) ? i : (parent[i] = find(parent[i]));
    }

    void unite(int x, int y) {
        int s1 = find(x); int s2 = find(y);
        if(s1 != s2) {
            if(rank[s1] < rank[s2]) {
                parent[s1] = s2;
            } else if(rank[s2] < rank[s1]) {
                parent[s2] = s1;
            } else { parent[s2] = s1; rank[s1]++; }
        }
    }
};


bool comparator(const std::vector<int>&a, const std::vector<int>&b) {
    return a[2] < b[2];
}


void Kruskal(std::vector<std::vector<int>>&edges, int n) {
    DSU dsu(n);
    std::sort(edges.begin(), edges.end(), comparator);
    std::vector<std::vector<int>>sol;

    int counter = 0; int cost = 0;

    for(const std::vector<int>&e : edges) {
        int s = e[0]; int d = e[1]; int c = e[2];
        if(dsu.find(s) != dsu.find(d)) {
            dsu.unite(s, d);
            cost += c;
            sol.push_back({s, d});
            if(++counter == n-1) break;
        }
    }

    fout << cost<<std::endl;
    fout<<n-1<<std::endl;
    for(const std::vector<int>& s : sol) {
        fout << s[1] <<  " " << s[0] << std::endl;
    }
}


int main(void) {
    int n, m, x, y, z;
    fin >> n >> m;
    std::vector<std::vector<int>>edges;

    for(int i=1;i<=m;++i) {
        fin >> x >> y >> z;
        edges.push_back({x, y, z});
    }

    Kruskal(edges, n);
    return 0;
}