#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,i,j,rx,x,ry,y,cnt,t[100001];
pair<int,int> sol[400001];
long long sum;


struct muchii{
    int i;
    int j;
    int value;
}v[400001];

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

    return x;
}

void update(int x, int rad){
    int y;
    while(x!=rad){
        y=t[x];
        t[x]=rad;
        x=y;
    }
}

bool cmp(muchii a, muchii b){
    if(a.value!=b.value)
        return a.value<b.value;
    else
        if(a.i!=b.i)
            return a.i<b.i;
        else
            return a.j<b.j;
}

int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++)
        t[i]=-1;

    for(i=1;i<=m;i++){
        fin>>v[i].i>>v[i].j>>v[i].value;
    }
    sort(v+1,v+m+1,cmp);


    for(i=1;i<=m;i++){
        x=v[i].i; y=v[i].j;
        rx=rad(x);
        update(x,rx);
        ry=rad(y);
        update(y,ry);
        if(rx!=ry){
            if(t[rx]>t[ry]){
                t[rx]+=t[ry];
                t[ry]=rx;
            }else{
                t[ry]+=t[rx];
                t[rx]=ry;
            }
            ///fout<<"DA\n";
            sum+=v[i].value;
            sol[++cnt].first=rx;
            sol[cnt].second=ry;
        }
    }

    fout<<sum<<"\n"<<n-1<<"\n";
    for(i=1;i<=cnt;i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";

    return 0;
}