#include <bits/stdc++.h>

using namespace std;

string name = "apm"; // apm
ifstream fin(name+".in");
ofstream fout(name+".out");

#if 1
#define cin fin
#define cout fout
#endif

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;

#define MAX 200001
#define MOD % 666013
#define tt cout << "* ";
#define m1 {cout << "-1";return 0;}
#define da {cout << "DA";return 0;}
#define nu {cout << "NU";return 0;}
#define afisare(d) {for(auto x : d) cout << x << ' '; cout << '\n';}


struct edge{
    int u, v, c;
    bool operator<(const edge& o) const {
        return c < o.c;
    }
};

vector<edge> edges, res;
vector<int> tree_id;
int n, m, cost = 0;

int main(){
    cin >> n >> m;
    tree_id.resize(n);

    for(int i=0; i<n; ++i)
        tree_id[i] = i;

    for(int i=0; i<m; ++i){
        int u, v, c;
        cin >> u >> v >> c;
        edges.push_back({u-1, v-1, c-1});
    }

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

    for(edge e : edges){
        if(tree_id[e.u] != tree_id[e.v]){
            cost += e.c + 1;
            res.push_back(e);

            int old_id = tree_id[e.u];
            int new_id = tree_id[e.v];

            for(int i=0; i<n; ++i)
                if(tree_id[i] == old_id)
                    tree_id[i] = new_id;
            }
    }
    cout << cost << '\n' << res.size() << '\n';
    for(edge x : res)
        cout << x.v+1 << ' ' << x.u+1 << '\n';

    return 0;
}