#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <fstream>
#define rosu 1
#define negru 2
using namespace std;
vector < pair<int,pair<int,int> > > L;
list <pair<int,int> > muchii;
int d[101], viz[101], tata[101], h[101], cost_total=0;
int n, m, x, y, c;
ifstream in("apm.in");
ofstream out("apm.out");
bool cmp(pair<int,pair<int,int> > a, pair<int,pair<int,int> > b){
    if(a.first <= b.first) return false;
    return true;
}
int find(int x){
    if(x==tata[x]) return x;
    return find(tata[x]);
}
void uniune(int a, int b){
    if(h[a] > h[b]){
        tata[b] = a;
    }
    else if( h[a] < h[b]){
        tata[a] = b;
    }else {
        tata[a] = b;
        h[a]++;
    }
}
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(), cmp);
    int k = 1;
    while(k <= n-1){
        auto K = L.back();
        L.pop_back();
        if(find(K.second.first) != find(K.second.second)){
            muchii.push_back({K.second.first, K.second.second});
            k++;
            cost_total+= K.first;
            uniune(K.second.first, K.second.second);
        }
    }
    out << cost_total << endl << muchii.size() << endl;
    for(auto i : muchii){
        out << i.first << ' ' << i.second << endl;
    }

    return 0;
}