#include <fstream>
#include <algorithm>
#define NMAX 200010
#define MMAX 400010
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,nr,rx,ry,s,t[NMAX];
struct muchie {
    int x,y,c;
    bool viz;
}v[MMAX];

bool cmp(muchie a,muchie b) {
    return a.c<=b.c;
}

int root(int x) {
    while (t[x]>0)
        x=t[x];
    return x;
}

int main() {
    fin>>n>>m;
    for (int i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,cmp);
    for (int i=1;i<=n;i++)
        t[i]=-1;
    for (int i=1;i<=m;i++) {
        rx=root(v[i].x);
        ry=root(v[i].y);
        if (rx!=ry) {
            if (-t[rx]>-t[ry]) {
                t[rx]+=t[ry];
                t[ry]=rx;
            }
            else {
                t[ry]+=t[rx];
                t[rx]=ry;
            }
            nr++;
            s+=v[i].c;
            v[i].viz=1;
        }
    }
    fout<<s<<"\n"<<nr<<"\n";
    for (int i=1;i<=m;i++)
        if (v[i].viz==1)
            fout<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}