#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

const int maxn = 200010;
const int maxm = 400010;

vector< pair< pii, int> > muchii;
vector< pii > sol;

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

class cmp{
    public:
    bool operator ()(const pair< pii, int> &a, const pair< pii, int> &b){
        return a.second < b.second;
    }
};

int tata[maxn], rang[maxn];

int root(int nod){
    int r = nod;
    while(tata[r] != r) r = tata[r];
    while(nod != r){
        int aux = tata[nod];
        tata[nod] = r;
        nod = aux;
    }

    return r;
}

void unite(int nod1, int nod2){
    if(rang[nod1] > rang[nod2]){
        tata[nod2] = nod1;
        rang[nod1] += rang[nod2];
    }
    else{
        tata[nod1] = nod2;
        rang[nod2] += rang[nod1];
    }
}
int main(){
    int n, m;
    f >> n >> m;
    for(int i = 0; i <= n; ++i) tata[i] = i, rang[i] = 1;
    for(int i = 1; i <= m; ++i){
        int a, b, c;
        f >> a >> b >> c;
        muchii.push_back({{a, b}, c});
    }
    sort(muchii.begin(), muchii.end(), cmp());
    int cost = 0;
    for(int i = 0; i < m; ++i){
        pair< pii, int > temp;
        temp = muchii[i];
        if(root(temp.first.first) != root(temp.first.second)){
            cost += temp.second;
            sol.push_back({temp.first.first, temp.first.second});
            unite(root(temp.first.first), root(temp.first.second));
        }
    }

    g << cost << '\n' << sol.size() << '\n';
    for(int i = 0; i < sol.size(); ++i){
        g << sol[i].first << ' ' << sol[i].second << '\n';
    }
    return 0;
}