#include <bits/stdc++.h>

using namespace std;

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

vector<pair<int, pair<int, int>>> edges;
int n,m, t[200005];

int root(int x) {
    if(t[x] == 0) return x;
    return root(t[x]);
}

int Union(int x, int y) {
    int rx = root(x);
    int ry = root(y);

    if(rx == ry) return 0;
    t[rx] = ry;
    return 1;
}

int main() {
    fin >> n >> m;
    while(m--) {
        int x, y, c;
        fin >> x >> y >> c;
        edges.push_back({c, {x, y}});
    }

    sort(edges.begin(), edges.end());

    int cost = 0;
    vector<pair<int, int>> ans;

    for(auto edge: edges) {
        int x = edge.second.first;
        int y = edge.second.second;
        int c = edge.first;

        if(Union(x, y)) {
            ans.push_back({x, y});
            cost += c; 
        }
        if(ans.size() == n-1) break;
    }
    fout << cost << '\n' << ans.size() << '\n';
    for(auto p: ans) fout << p.first << ' ' << p.second << '\n';
}