#include <bits/stdc++.h>
using namespace std;

struct erikfzf {
    int x;
    int y;
    int v;
    
    bool operator<(const erikfzf &a) const {
        return v < a.v;
    }
};

struct DSU {
    int n;
    vector<int> a;
    vector<int> cnt;
    
    DSU(int N) {
        n = N;
        a.resize(n);
        cnt.resize(n);
        for(int i = 0; i < n; i ++) {
            a[i] = i;
            cnt[i] = 1;
        }
    }

    int leader(int x) {
        if(x == a[x])
            return x;
        return a[x] = leader(a[x]);
    }

    void merge(int x, int y) {
        x = leader(x);
        y = leader(y);
        if(cnt[x] > cnt[y])
            swap(x, y);
        a[x] = y;
        cnt[y] += cnt[x];
    }

    bool issame(int x, int y) {
        x = leader(x);
        y = leader(y);
        return x == y;
    }
};

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m; cin >> n >> m;

    vector<erikfzf> a; 

    for(int i = 0; i < m; i ++) {
        int x, y, v; cin >> x >> y >> v; x--; y --;
        a.push_back({x, y, v});
    }

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

    DSU dsu(n);

    vector<erikfzf> ans;
    int ansv = 0;

    for(int i = 0; i < m; i ++) {
        if(dsu.issame(a[i].x, a[i].y))
            continue;
        ansv += a[i].v;
        ans.push_back(a[i]);
        dsu.merge(a[i].x, a[i].y);
    }

    cout << ansv << '\n';
    cout << n - 1 << '\n';

    for(auto i : ans) {
        cout << i.x + 1 << ' ' << i.y + 1 << '\n';
    }


}