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

#define VMAX 200005

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

int E, V, tata[VMAX], cost_total;

struct muchie{
    int u, v, cost;
};
vector<muchie> edges, apm;

bool cmp(muchie a, muchie b){
    return a.cost < b.cost;
}

int find(int t){
    if(tata[t] == t)
        return t;
    return tata[t] = find(tata[t]);
}

int main(){
    f >> V >> E;
    for(int i = 1; i <= E; i++){
        int x, y, c;
        f >> x >> y >> c;
        edges.push_back({x, y, c});
    }

    sort(edges.begin(), edges.end(), cmp);
    for(int i = 1; i <= V; i++)
        tata[i] = i;

    for(auto& m : edges){
        int ru = find(m.u), rv = find(m.v);

        if(ru != rv){
            tata[ru] = rv;
            cost_total += m.cost;
            apm.push_back(m);
        }

        if(apm.size() == V - 1)
            break;
    }

    g << cost_total << '\n' << V - 1 << '\n';
    for(auto x : apm)
        g << x.u << ' ' << x.v << '\n';
}