#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using edge = tuple<int, int, int>;
int n,m;
vector<edge> Edges;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct DSU {
    int n;
    vector<int> t, sz;
    DSU(int _n){
        n = _n;
        t.resize(n+1);
        sz.resize(n+1);
        for(int i = 1; i <= n; i++){
            t[i] = i;
            sz[i] = 1;
        }
    }
    int root(int nod){
        if(t[nod] == nod){
            return nod;
        }
        return t[nod] = root(t[nod]);
    }
    void join(int x, int y){
        x = root(x);
        y = root(y);
        if(sz[x] < sz[y]){
            swap(x, y);
        }
        sz[x] += sz[y];
        t[y] = x;
    }
    bool areJoined(int x, int y){
        return root(x) == root(y);
    }
};

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        fin >> x >> y >> c;
        Edges.push_back({c, x, y});
    }
    sort(Edges.begin(), Edges.end());
    DSU ds(n);
    int ans = 0;
    vector<pii> apm;
    for(auto [cost, x, y]: Edges){
        if(!ds.areJoined(x, y)){
            ans += cost;
            ds.join(x, y);
            apm.push_back({x,  y});
        }
    }
    fout << ans << "\n" << apm.size() << "\n";
    for(auto [x, y]: apm){
        fout << x << " " << y << "\n";
    }
    return 0;
}