#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int t[101];
int costApm;
vector<pair<int, int> > apm;
vector<tuple<int, int, int> > G;

void read() {
    f >> n >> m;
    for(int i=0; i<m; i++) {
        int x, y, cost;
        f >> x >> y >> cost;
        G.push_back(make_tuple(cost, x, y));
    }
}

int getRoot(int nod) {
    if(t[nod] == nod)
        return nod;
    t[nod] = getRoot(t[nod]);
    return t[nod];
}

void kruskal () {
   
    sort(G.begin(), G.end());

    for(int i=1; i<=n; i++) 
        t[i] = i;

    for(auto it : G) {

        int x, y, cost;
        tie(cost, x, y) = it;

        int rx = getRoot(x);
        int ry = getRoot(y);

        if(rx != ry) {
            costApm += cost;
            t[rx] = ry;
            apm.push_back(make_pair(x, y));
        }

    }

}

int main() {

    read();
    kruskal();

    g << costApm << '\n' << apm.size() << '\n';


    for(int i=0; i<apm.size(); i++, cout<<'\n')
        g<< apm[i].first << " " << apm[i].second; 
    
    return 0;
}