#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

void read(int &n, int &m, vector< pair<int, pair<int, int> > >  &G) {
    ifstream fin("apm.in");
    if(!fin.is_open()) {
        cout << "The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }

    fin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        G.push_back(make_pair(z, make_pair(x, y)));
    }

    fin.close();
}

void Kruskal(int n, int m, vector< pair<int, pair<int, int> > >  G) {
    sort(G.begin(), G.end());
    int *vis = new int[n + 1];
    fill(vis, vis + n + 1, 0);
    for(int i = 1; i <= n; ++i)
        vis[i] = i;

    int ct = 0;
    vector< pair<int, int> > sol;
    for(int k = 1; k <= n - 1; ++k) {
        int i = 0;
        while(vis[G[i].second.first] == vis[G[i].second.second])
            ++i;
        ct += G[i].first;
        int aux = vis[G[i].second.second];
        sol.push_back(make_pair(G[i].second.first,G[i].second.second));
        for(int j = 1; j <= n; ++j)
            if(vis[j] == aux)
                vis[j] = vis[G[i].second.first];
    }
    ofstream out("apm.out");
    out << ct << '\n';
    out << sol.size() << '\n';
    for(vector<pair<int, int> >::iterator it = sol.begin(); it != sol.end(); ++it)
        out << it->first << ' ' << it->second << '\n';
    out.close();
}

int main() {
    int n, m;
    vector<pair<int, pair<int, int> > > G;
    read(n, m, G);
    Kruskal(n, m, G);
    return 0;
}