#include <iostream>
#include <fstream>
#include <algorithm>
#define mod 100005
#define x first
#define y second

using namespace std;

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

int n,m,t[100005],i,q,rx,ry,x,y,j,cost,k;

pair <int,int> s[200001];
pair <int ,pair<int,int> >a[400005];

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


int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++)
        t[i]=-1;
    for(j=1;j<=m;j++){
        fin>>a[j].y.x>>a[j].y.y>>a[j].x;
}
sort(a+1,a+m+1);
for(j=1;j<=m;j++){
        int xx=a[j].y.x;
        int  yy=a[j].y.y;
        rx=rad(xx);
        ry=rad(yy);
        if(rx==ry){
            continue;
        }
        else{
            cost+=a[j].x;
            s[++k].x=xx;
            s[k].y=yy;
            if(t[rx]<t[ry]){
                t[rx]+=t[ry];
                t[ry]=rx;
            }
            else{
                t[ry]+=t[rx];
                t[rx]=ry;
            }
    }
}


    fout<<cost<<"\n"<<k<<"\n";
    for(i=1;i<=k;i++)
        fout<<s[i].x<<" "<<s[i].y<<"\n";
    }