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

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

struct muchie {
    int x, y, val;
};

int n, m, cnt, cost, parent[200005];
vector<muchie> v;
vector<pair<int, int>> ans;

int set_find(int x) {
    if(x == parent[x])
        return x;
    else return parent[x] = set_find(parent[x]);
}

void dsu(int a, int b) {
    int pa = set_find(a);
    int pb = set_find(b);

    parent[pa] = pb;
}

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

int main()
{
    in >> n >> m;
    v.resize(m);
    for(int i=0; i<m; i++) {
        in >> v[i].x >> v[i].y >> v[i].val;
    }
    for(int i=1; i<=n; i++)
        parent[i] = i;

    sort(v.begin(), v.end(), cmp);

    for(int i=0; i<m; i++) {
        if(set_find(v[i].x) != set_find(v[i].y)) {
            cnt++;
            cost += v[i].val;
            dsu(v[i].x, v[i].y);
            ans.push_back({v[i].x, v[i].y});
        }
        if(cnt == n - 1)
            break;
    }

    out << cost << '\n' << n - 1 << '\n';
    for(auto elm : ans)
        out << elm.first << ' ' << elm.second << '\n';
    return 0;
}