#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 400010;
int x[NMAX], y[NMAX], c[NMAX], id[NMAX], gr[NMAX], ans, n, m;
vector < int >  v;

bool cmp(const int &i, const int &j){
    return c[i] < c[j];
}

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);
}

int main(){
    int i,j;
    f >> n >> m;
    for(i = 1 ; i <= m ; i++){
        f >> x[i] >> y[i] >> c[i];
        id[i] = i;
    }

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

    sort(id + 1, id + m + 1, cmp);

    for(i = 1 ; i <= m ; i++)
    if(grupa(x[id[i]]) != grupa(y[id[i]])){
        ans += c[id[i]];
        reuniune(x[id[i]], y[id[i]]);
        v.push_back(id[i]);
    }

    g << ans << "\n" << v.size() << "\n";
    for(i = 0 ; i < v.size() ; i++)
        g << x[v[i]] << " " << y[v[i]] << "\n";

    return 0;
}