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

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

#define cin fin
#define cout fout

int find_set(int v) {
    if(v == sg[v])
        return v;
    return find_set(sg[v]);
}
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if(a != b)
        sg[b] = a;
}

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(find_set(x) == find_set(y)) continue;
        
        sv[k] = {x, y};
        k++;
        s += c;
        
        union_sets(x, y);
    }
    
    cout << s << '\n' << n - 1 << '\n';
    for(int i = 0; i < k; ++i) cout << sv[i].f << ' ' << sv[i].s << '\n';
}