#include <bits/stdc++.h>

std::ifstream input("apm.in");
std::ofstream output("apm.out");

typedef std::pair<int, int> PII;
typedef std::pair<int, PII> PIII;

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

        int find_set(int v) {
            if (v == parent[v])
                return v;
            return parent[v] = find_set(parent[v]);
        }

        void union_sets(int a, int b) {
            a = find_set(a);
            b = find_set(b);
            if (a != b) {
                if (size[a] < size[b])
                    std::swap(a, b);
                parent[b] = a;
                size[a] += size[b];
            }
        }
};

int main () {

    int n;
    input >> n;
    std::vector<std::vector<int>> solutionGraph(n+1);

    int m;
    input >> m;
    std::vector<PIII> graph(m);
    //first - cost
    //first.first - node1
    //first.second - node2

    for(int i = 1; i <= m; i++){
        int x, y, c;
        input >> x >> y >> c;
        graph.push_back({c, {x, y}});
    }

    std::sort(graph.begin(), graph.end());
    DSU dsGraph(n+1);

    int cost = 0;

    for(auto edge : graph){
        int c = edge.first;
        int x = edge.second.first;
        int y = edge.second.second;

        if(dsGraph.find_set(x) != dsGraph.find_set(y)){
            dsGraph.union_sets(x, y);
            cost += c;
            solutionGraph[x].push_back(y);
            solutionGraph[y].push_back(x);
        }
    }

    output << cost << "\n" << n-1 << "\n";
    for(int i = 1; i <= n; i++){
        for(auto node : solutionGraph[i]){
            if(i < node){
                output << i << " " << node << "\n";
            }
        }
    }

    return 0;
}