#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second

#define cin fin
#define cout fout

void tr(int *a, int n, int x, int y) {
    for(int i = 0; i < n; ++i)
        if(a[i] == x) a[i] = y;
}

int32_t main() {
    ios_base::sync_with_stdio(0); //cin.tie(0); cout.tie(0);
    
    fstream fin("apm.in");
    fstream fout("apm.out");
    
    int n, m; cin >> n >> m;
    pair<pair<int, int>, int> a[m];
    int sg[n + 1]; for(int i = 0; i <= n; ++i) sg[i] = i;
    for(int i = 0; i < m; ++i) {
        int x, y, c; cin >> x >> y >> c;
        if(x > y) swap(x, y);
        a[i] = {{x, y}, c};
    }
    sort(a, a + m, [](auto a, auto b) {
        if(a.s == b.s) return a < b;
        return a.s < b.s;
    });
    
    vector<pair<int, int>> sv; int s = 0;
    for(int i = 0; i < m; ++i) {
        int x = a[i].f.f, y = a[i].f.s, c = a[i].s;
        
        if(sg[x] == sg[y]) continue;
        
        sv.push_back({x, y});
        s += c;
        
        tr(sg, n + 1, sg[y], sg[x]);
    }
    
    cout << s << '\n' << n - 1 << '\n';
    for(auto &x : sv) cout << x.f << ' ' << x.s << '\n';
}