#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
const int N = 102;
vector<pair<int, pair<int, int>> > V;
int F[N], sz[N];
int Find(int x){
    int root = x;
    while(root != F[root])
        root = F[root];
    while(x != F[x]){
        int aux = F[x];
        F[x] = root;
        x = aux;
    }
    return root;
}
void Unite(int x, int y){
    int m1 = Find(x), m2 = Find(y);
    if(sz[m1] < sz[m2]){
        sz[m2] += sz[m1];
        F[m1] = m2;
    }
    else{
        sz[m1] += sz[m2];
        F[m2] = m1;
    }
}
int mst_w = 0;
vector<pair<int, int> > rez;
void Kruskal(){
    sort(V.begin(), V.end());
    vector<pair<int, pair<int, int>> >::iterator it;
    for(it = V.begin(); it != V.end(); it++){
        int u = (*it).second.first, v = (*it).second.second;
        if(Find(u) != Find(v)){
            rez.push_back({u, v});
            mst_w += (*it).first;
            Unite(u, v);
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        F[i] = i;
        sz[i] = 1;
    }
    for(int i=1; i<=m; i++){
        int x1, x2, c;
        cin >> x1 >> x2 >> c;
        V.push_back({c, {x1, x2}});
    }
    Kruskal();
    cout << mst_w << '\n' << rez.size() << '\n';
    for(int i=0; i<rez.size(); i++){
        cout << rez[i].first << ' ' << rez[i].second << '\n';
    }
    return 0;
}