#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

struct MUCHIE{ int x,y,cost; };

int comp(const void* a,const void* b){

    return ((MUCHIE*)a)->cost-((MUCHIE*)b)->cost;
    }

void MakeSet(int i,int *p,int *h){

    p[i]=0;
    h[i]=0;

}
int FindSet(int i,int *p){

    if(p[i]==0)
        return i;
    else
        p[i]=FindSet(p[i],p);
    return p[i];
    }
void Union(int i,int j,int *p,int *h){

    i=FindSet(i,p);
    j=FindSet(j,p);

    if(h[i]>h[j])
        p[j]=i;
    else
        {
            p[i]=j;
            if(h[i]==h[j])
                h[j]++;
        }
}
class Graf{
    int v,e;
    MUCHIE *E;
public:
    Graf(){}
    Graf(int x){
        e=x;
        E=new MUCHIE[e];
        }
    Graf(char* numeFisier){

    ifstream f(numeFisier);
    f>>v>>e;

    E=new MUCHIE[e];
    for(int i=0;i<e;i++)
        f>>E[i].x>>E[i].y>>E[i].cost;

    qsort(E,e,sizeof(MUCHIE),comp);

    f.close();
    }
    Graf Kruskal();
    int Cost();
    void descrieGraf(char* numeFisier){

        ofstream f(numeFisier);
        f<<(this->Cost())<<" "<<e<<"\n";
        for(int i=0;i<e;i++)
            f<<E[i].x<<" "<<E[i].y<<"\n";
        f.close();

}
};

Graf Graf::Kruskal(){

    Graf T(v-1);
    int parinte[v],inaltime[v],k=0;

    for(int i=0;i<v;i++)
        MakeSet(i,parinte,inaltime);

    for(int i=0;i<e;i++){
        if(FindSet(E[i].x,parinte)!=FindSet(E[i].y,parinte))
        {

            T.E[k++]=E[i];
            Union(E[i].x,E[i].y,parinte,inaltime);
        }
        if(k==v-1)
            break;
    }

    return T;

}
int Graf::Cost(){

    int c=0;
    for(int i=0;i<e;i++)
        c+=E[i].cost;
    return c;
}

int main(){
    Graf G("apm.in");
    G.Kruskal().descrieGraf("apm.out");
}