#include <algorithm>
#include <fstream>

#define NMAX 400005

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int gr[NMAX] , x[NMAX] , y[NMAX] , cost[NMAX] , aux[NMAX];
int n , m , sol;

vector <int> ans;

int grupa(int i) {
    if(gr[i] == i)
        return i;

    gr[i] = grupa(gr[i]);
    return gr[i];
}

void reuniune(int i , int j) {
    gr[grupa(i)] = grupa(j);
}

bool comp(int a , int b) {
    return cost[a] < cost[b];
}

int main() {
    f >> n >> m;
    for(int i = 1 ; i <= m ; ++i) {
        f >> x[i] >> y[i] >> cost[i];
        aux[i] = i;
    }

    for(int i = 1 ; i <= n ; ++i) {
        gr[i] = i;
    }

    sort(aux + 1 , aux + m + 1 , comp);
    for(int i = 1 ; i <= m ; ++i) {
        if(grupa(x[aux[i]]) != grupa(y[aux[i]])){
            sol += cost[aux[i]];
            reuniune(x[aux[i]],y[aux[i]]);
            ans.push_back(aux[i]);
        }
    }

    g << sol << '\n' << n - 1 << '\n';
    for(int i = 0 ; i < n - 1; ++i) {
        g << y[ans[i]] << " " << x[ans[i]] << '\n';
    }
    return 0;
}