#include <fstream>
#include <vector>
#include <list>
using namespace std;
ifstream in("apm.in");
ofstream cout("apm.out");
vector<pair<int, pair<int,int> > > L;
int x, y, c, n, m, k, tata[200001], h[101];
list < pair<int, int> > E;
long long sum = 0;
int find(int x){
    if(tata[x]==x)
        return x;
    return find(tata[x]);
}
void uni(int a, int b){
    if(h[a] > h[b]) {
        tata[b] = a;
        return;
    }
    if(h[b] > h[a]) {
        tata[a] = b;
        return;
    }
    tata[a] = b;
    h[b] ++ ;
}
int main() {

    in >> n >> m;
    for (int i = 1; i <= m; i++){
        in >> x >> y >> c;
        L.push_back({c,{x,y}});
    }
    for(int i=1;i<=n;i++) {
        tata[i] = i;
        h[i] = 0;
    }

    sort(L.begin(), L.end());

    while(k<n-1){
        pair<int, pair<int,int> > K = L[0];
        L.erase(L.begin());
        if(find(K.second.first) != find(K.second.second)){
            k++;
            sum += (K.first);
            E.push_back({K.second.first, K.second.second});
            uni(K.second.first, K.second.second);
        }
    }
    cout << sum << endl;
    cout << E.size() << endl;
    for(auto p : E){
        cout << p.first << ' ' << p.second << endl;
    }
    return 0;
}