#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, lg[200005];
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[b]=a; lg[a]+=lg[b];}
    else {t[a]=b; lg[b]+=lg[a];}
}
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=rad(v[i].se.fi);
        y=rad(v[i].se.se);
        if (x!=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;
}