#include <bits/stdc++.h>

using namespace std;

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

bool cmp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b){
    return a.first < b.first;
}

int f[200005];

int find_father(int x){
    if(f[x] == x) return x;
    f[x] = find_father(f[x]);
    return f[x];
}

void add(int a, int b){
    int f1 = find_father(a);
    int f2 = find_father(b);
    f[f1] = f2;
}

bool same_set(int a, int b){
    return find_father(a) == find_father(b);
}

int main(){
    cin.tie(0);ios::sync_with_stdio(0);

    int n, m;
    fin >> n >> m;

    vector < pair<int, pair<int, int> > > v;
    for(int i = 0; i < m; i++){
        int l, r, c; fin >> l >> r >> c;
        pair< int, pair<int, int> > p;
        p.first = c;
        p.second.first = l;
        p.second.second = r;
        v.push_back( p );
    }

    for(int i = 1; i <= n; i++) f[i] = i;

    sort(v.begin(), v.end(), cmp);
        
    int cost = 0;
    vector < pair<int, int> > sol;
    for(int i = 0; i < m; i++){
        if( same_set( v[i].second.first, v[i].second.second  ) ) continue;
        add( v[i].second.first, v[i].second.second );
        cost += v[i].first;
        sol.push_back( make_pair( v[i].second.first, v[i].second.second ) );
    }

    fout << cost << endl << sol.size() << endl;
    for(int i = 0; i < sol.size(); i++){
        fout << sol[i].first << " " << sol[i].second << endl;
    }






    return 0;
}