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

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
class GrafC {
private:
   unordered_map<int, vector<pair<int, int>>> graf;
   vector<int> t;
   vector<int> h;
   int n;

public:
    GrafC(int n) {
        this->n = n+1;
        h.resize(n);
        t.resize(n);
    }
    void add(int s, int d, int cost) {
        graf[s].emplace_back(d, cost);
    }
    void Init(int u){
        t[u]=h[u]=0;
    }
    int Reprez(int u){
        while(t[u]!=0)
            u=t[u];
        return u;
    }
    void Union(int u, int v) {
        int ru, rv;
        ru = Reprez(u);
        rv = Reprez(v);
        if (h[ru] > h[rv])
            t[rv] = ru;
        else {
            t[ru] = rv;
            if (h[ru] == h[rv])
                h[rv]++;
        }
    }
    vector<pair<int, pair<int, int>>> kruskal() {
        vector<pair<int, pair<int, int>>> rez;
        vector<pair<int, pair<int, int>>> muchii;
        for (auto x = graf.begin(); x != graf.end(); ++x) {
            for (auto mch : x->second) {
                muchii.push_back({mch.second, { x->first, mch.first}});
            }
        }
        sort(muchii.begin(), muchii.end());
        for (auto mch : muchii) {
            int ru = Reprez(mch.second.first);
            int rv = Reprez(mch.second.second);
            if (ru != rv) {
                rez.push_back(mch);
                Union(ru, rv);
            }
        }

        return rez;
    }
};
int main() {
    int n,m;
    fin>>n>>m;
    GrafC g(n);
    for(int i=0;i<m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        g.add(x,y,c);
    }
    vector<pair<int, pair<int, int>>> apm = g.kruskal();
    int cost_tot=0;
    for(auto x:apm)
        cost_tot+=x.first;
    fout<<cost_tot<<"\n"<<apm.size()<<"\n";
    for(auto x:apm)
        fout<<x.second.first<<" "<<x.second.second<<"\n";
    return 0;
}