#include <fstream>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct vecin {
    int next, cost;
};

struct muchie {
    int a, b;
};

struct muchie_prim {
    int cost, tata, to_join;
    bool operator < (const muchie_prim &other) const {
        return cost > other.cost;
    }
};

vector<vecin> vecini[int(2e5) + 5];
priority_queue<muchie_prim> pq;
vector<muchie> v;
int root[int(2e5) + 5];
int sz[int(2e5) + 5];
int cost_total = 0;

int find_root(int x){
    if (root[x] == x)
        return x;

    root[x] = find_root(root[x]);
    return root[x];
}
void join(int root_1, int root_2){
    if (sz[root_1] < sz[root_2]){
        swap(root_1, root_2);
    }

    root[root_2] = root_1;
    sz[root_1] += sz[root_2];
}



int main(){

    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++){
        int a, b, cost;
        fin >> a >> b >> cost;
        vecini[a].push_back({b, cost});
        vecini[b].push_back({a, cost});
    }

    for (int i = 1; i <= n; i++){
        sz[i] = 1;
        root[i] = i;
    }

    for (vecin vec: vecini[1]){
        pq.push({vec.cost, 1, vec.next});
    }

    while (!pq.empty()){
        while (!pq.empty() && find_root(root[pq.top().tata]) == find_root(root[pq.top().to_join]))
            pq.pop();

        if (pq.empty()){
            break;
        }

        muchie_prim top = pq.top();
        pq.pop();
        int root_1 = find_root(top.tata);
        int root_2 = find_root(top.to_join);
        join(root_1, root_2);

        cost_total += top.cost;
        v.push_back({top.tata, top.to_join});

        for (vecin vec: vecini[top.to_join]){
            if (vec.next == top.tata)
                continue;

            pq.push({vec.cost, top.to_join, vec.next});
        }

    }

    fout << cost_total << '\n';
    fout << v.size() << '\n';
    for (muchie m: v){
        fout << m.a << " " << m.b << '\n';
    }
    return 0;
}