#include <fstream>
#include <queue>
#include <functional>
#include <vector>

using namespace std;

const int MAXN = 2e5;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct Edge{
    int u, v, cost;
};

struct DisjointSet{
    int p[MAXN+1];
    int r[MAXN+1];
};

struct comp{
    bool operator () (const Edge &a, const Edge &b){
        return a.cost > b.cost;
    }
};
priority_queue<Edge, vector<Edge>, comp> e;

DisjointSet init_ds(int n){
    DisjointSet ds;
    for(int i = 1; i <= n; ++i) {
        ds.p[i] = i;
        ds.r[i] = 1;
    }
    return ds;
}

int find(DisjointSet &ds, int node){
    if (ds.p[node] == node)
        return node;
    ds.p[node] = find(ds, ds.p[node]);
    return ds.p[node];
}

void join(DisjointSet &ds, int u, int v){

    if (ds.r[u] < ds.r[v]) {
        ds.p[u] = v;
    } else if (ds.r[v] < ds.r[u]) {
        ds.p[v] = u;
    } else {
        ds.p[v] = u;
        ds.r[u]++;
    }

}

void kruskal(int &mst_cost, vector<pair<int, int>> &mst, DisjointSet &ds){

    while (!e.empty()){
        Edge edge = e.top();
        e.pop();

        int pu = find(ds, edge.u);
        int pv = find(ds, edge.v);

        if (pu != pv){ // edge on the mst
            mst_cost += edge.cost;
            mst.push_back(make_pair(edge.u, edge.v));
            join(ds, pu, pv);
        }
    }
}

int main() {
    int n, m;

    cin >> n >> m;

    while (m--) {
        int u, v, cost;
        cin >> u >> v >> cost;
        e.push(Edge{u, v, cost});
    }


    int mst_cost = 0;
    vector<pair<int, int>> mst;
    mst.clear();
    DisjointSet ds = init_ds(n);

    kruskal(mst_cost, mst, ds);

    cout << mst_cost << "\n" << n-1 << "\n";
    for (auto edge : mst)
        cout << edge.first << " " << edge.second << "\n";

    return 0;
}