#include <fstream>
#include <algorithm>

using namespace std;

int v[200005];
int n,m,i,k,x1,y1,t;

struct apm {
                int x;
                int y;
                int c;
            } a[400005], sol[200005];

bool cmp(const apm &a, const apm &b) {
    return a.c<b.c;
}

int rad(int x) {
    while(v[x]>0)
        x=v[x];
    return x;
}

int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    k=0;
    for(i=1;i<=m;i++)
        f>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+m+1,cmp);

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

    i=0;
    while(k<n-1) {
        i++;
        x1=rad(a[i].x);
        y1=rad(a[i].y);
        if(x1!=y1) {
            if(v[x1]<v[y1]) {
                t+=a[i].c;
                k++;
                sol[k].x=a[i].x;
                sol[k].y=a[i].y;
                v[x1]+=v[y1];
                v[y1]=x1;
            }
            else{
                t+=a[i].c;
                k++;
                sol[k].x=a[i].x;
                sol[k].y=a[i].y;
                v[y1]+=v[x1];
                v[x1]=y1;
            }
        }
    }
    g<<t<<"\n"<<k<<"\n";
    for(i=1;i<=k;i++)
        g<<sol[i].x<<" "<<sol[i].y<<"\n";
    return 0;
}