#include <bits/stdc++.h>
#define se second
#define fi first
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
pair<int, pair<int, int>>v[400005];
int fr[400005], n, m, i, x, y, cf, t[200005], k;
int lg(int a) {
    int l;
    while (a!=t[a]) {
        l++;
        a=t[a];
    }
    return l;
}
int rad(int a) {
    if (t[t[a]]==t[a]) return t[a];
     return rad(t[a]);
}
void uneste(int a, int b) {
    if (lg(a)>lg(b)) t[rad(b)]=a;
    else t[rad(a)]=b;
}
int main()
{
    fin>>n>>m;
    for (i=1; i<=n; i++) t[i]=i;
    for (i=1; i<=m; i++) {
        fin>>v[i].se.fi>>v[i].se.se>>v[i].fi;
    }
    sort(v+1, v+m+1);
    for (i=1; i<=m; i++) {
        if (k==n-1) break;
        x=v[i].se.fi;
        y=v[i].se.se;
        if (rad(x)!=rad(y)) {
            uneste(x, y);
            fr[i]=1;
            cf+=v[i].fi;
            k++;
        }
    }
    fout<<cf<<'\n'<<n-1<<'\n';
    for (i=1; i<=m; i++) {
        if (fr[i]==1) fout<<v[i].se.fi<<' '<<v[i].se.se<<'\n';
    }
    return 0;
}