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


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


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

        for(int i=1;i<=V;++i) {
            rank[i] = 1;
        }
    }

    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::vector<std::vector<int>>res; 
    std::sort(edges.begin(), edges.end(), comparator);
    int cost = 0; int count = 0;

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

    fout << cost << std::endl;
    fout<< n-1 << std::endl;
    for(const std::vector<int>&muchie : res) {
        fout << muchie[1] << " " << muchie[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;
}