#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(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();
    }
    void Kruskal(char*);
    int Cost();
};

void Graf::Kruskal(char* numeFisier){

    int parinte[v],inaltime[v],r[e],s=0,k=0;

    for(int i=0;i<e;i++)
        r[i]=0;
    for(int i=0;i<e;i++)
        MakeSet(i,parinte,inaltime);

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

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

    ofstream f(numeFisier);
    f<<s<<" "<<k<<"\n";
    for(int i=0;i<e;i++)
        if(r[i])
            f<<E[i].x<<" "<<E[i].y<<"\n";
    f.close();

}


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