#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m, parent[200005], visited[200005], chosen, ansCost, rnk[200005];

int getParent(int n){
    if(n != parent[n])
        return getParent(parent[n]);
    else
        return n;
}

void unite(int p, int x){
    while(x != parent[x]) {
        int temp = parent[x];
        parent[x] = p;
        x = temp;
    }
    parent[x] = p;
}

struct muchie{
    int x1, x2, cost;
};

inline bool cmp(muchie a, muchie b){
    return a.cost < b.cost;
}

int main() {
    vector<muchie> v, ans;
    muchie t;
    f >> n >> m;
    for(int i = 1; i <= m; i ++){
        f >> t.x1 >> t.x2 >> t.cost;
        v.push_back(t);
    }

    for(int i = 1; i <= n; i ++){
        parent[i] = i;
        rnk[i] = 1;
    }

    sort(v.begin(), v.end(), cmp);

    for(auto c : v){
        int p1 = getParent(c.x1);
        int p2 = getParent(c.x2);
        if(p1 != p2){
            ans.push_back(c);
            ansCost += c.cost;
            if(rnk[p1] < rnk[p2]){
                unite(p2, c.x1);
                rnk[p2] += rnk[p1];
            }
            else {
                unite(p1, c.x2);
                rnk[p1] += rnk[p2];
            }
            chosen ++;
            if(chosen == n - 1)
                break;
        }
    }
    g << ansCost << "\n" << chosen << "\n";
    for(auto mm : ans){
        g << mm.x1 << " " << mm.x2 << "\n";
    }
    return 0;
}