#include<fstream>
#include<vector>
#include<utility>
#include<algorithm>

#define pi pair<int, int>
#define pipi pair<int, pair<int, int>>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

vector<int> par;
vector<int> sz;

int comp(int u){
    return par[u] = ((par[u] == u)?u:comp(par[u]));
}

bool un(int u, int v){
    u = comp(u);
    v = comp(v);
    if(u == v) return false;
    if(sz[u] > sz[v]) swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
    return true;
}

int main(){
    int u, v, w;
    int n, m;
    cin >> n >> m;
    vector<pipi> gr(m), mst;
    for(int i = 0; i < m; i++){
        cin >> u >> v >> w;
        u--;
        v--;
        gr[i] = pipi(w, pi(u, v));
    }
    sort(gr.begin(), gr.end());
    par.resize(n);
    sz.resize(n);
    for(int i = 0; i < n; i++){
        par[i] = i;
        sz[i] = 1;
    }
    
    int sum = 0;
    
    for(int i = 0; i < m; i++)
        if(un(gr[i].second.first, gr[i].second.second)){
            mst.push_back(gr[i]);
            sum += gr[i].first;
    }
    
    cout << sum << '\n' << n - 1 << '\n';
    
    for(int i = 0; i < n - 1; i++)
        cout << mst[i].second.first + 1 << ' ' << mst[i].second.second + 1 << '\n';
    
    return 0;
}