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

using namespace std;

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

int FComp(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 e,v;
    MUCHIE *E;
public:
    Graf(){}
    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),FComp);
    }
    Graf Kruskal(int&, int&);
    void AfMuchii(char*);
    };

Graf Graf::Kruskal(int& s,int& k){
    Graf T;
    T.e=v-1;
    T.E=new MUCHIE[T.e];

    int parinte[v],inaltime[v];
    s=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];
            s+=E[i].cost;
            Union(E[i].x,E[i].y,parinte,inaltime);
        }
        if(k==v-1)
            break;
    }
    return T;
}
void Graf::AfMuchii(char* numeFisier){
    FILE *f=fopen(numeFisier,"a");

    for(int i=0;i<e;i++)
        fprintf(f,"%d %d\n",E[i].x,E[i].y);
    }

int main(){

    int cost,muchii;
    Graf G("apm.in"),APM;
    APM=G.Kruskal(cost,muchii);
    ofstream f("apm.out");
    f<<cost<<"\n"<<muchii<<"\n";
    APM.AfMuchii("apm.out");
    }