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

pair<pair<int, int>, int> a[(int)(4 * 1e5)];
int sg[(int)(2 * 1e5 + 1)];
pair<int, int> sv[2 * (int)1e5];

#define cin fin
#define cout fout

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

int32_t main() {
    ios_base::sync_with_stdio(0); //cin.tie(0); cout.tie(0);
    
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    
    int n, m; cin >> n >> m;
    
    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;
    });
    
    int s = 0, k = 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[k] = {x, y};
        k++;
        s += c;
        
        tr(n + 1, sg[y], sg[x]);
    }
    
    cout << s << '\n' << n - 1 << '\n';
    for(int i = 0; i < k; ++i) cout << sv[i].f << ' ' << sv[i].s << '\n';
}