#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int t[100100],x,y,n,p,op,rx,ry,s,k,c;
pair<int, pair<int,int> > pereche[400010];
pair<int,int> sol[400100];
int rad(int xx){
    while(t[xx]>0){
        xx=t[xx];
    }
    return xx;
}

int main(){
    fin>>n>>p;
    for(int i=1;i<=n;i++){
        t[i]=-1;
    }
    for(int i=1;i<=p;i++){
        fin>>pereche[i].second.first>>pereche[i].second.second>>pereche[i].first;

    }
    sort(pereche+1,pereche+p+1);

    for(int i=1;i<=p;i++){
        x=pereche[i].second.first;
        y=pereche[i].second.second;
        rx=rad(x);
        ry=rad(y);
        c=pereche[i].first;
        if(rx!=ry){

            if(t[rx]<t[ry]){
                t[rx]+=t[ry];
                t[ry]=rx;
            }
            else{
                t[ry]+=t[rx];
                t[rx]=ry;
            }

            k++;
            sol[k].first=x;
            sol[k].second=y;
            s+=c;
        }




     }


   fout<<s<<"\n"<<k<<"\n";
   for(int i=1;i<=k;i++){
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
   }





}