#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define INFINIT 1000000
struct nod
{
    int info;
    nod *adr_urm;
};
nod **v;
int *cheie,*p,*used,N,M,r,**m,nrmuchii,S;///cheie pt costul minim,p pt vectorul de tati,used pt a vedea daca nodul a fost selectat sau nu;
int extrageMinim(int &tata)
{
    int i,u,max=1000000;
    for(i=1;i<=N;++i)
        if(used[i]==1)                              //trebuie sa cautam in vecinii unui nod deja selectat,ot a vedea cel mai apropiat nod de el;
        {
            nod *p=v[i];
            while(p)
            {
                if(m[i][p->info]<max && used[p->info]==0)///alegem cel mai apropiat nod neselectat
                    {u=p->info;max=m[i][p->info];tata=i;}///tinem minte si nodul tata
                p=p->adr_urm;
            }
        }
    used[u]=1;///il marcam ca selectat;
    return u;

}
void APCM_Prim()
{
    int c,u,cop=N;
    for(c=1;c<=N;++c)
        cheie[c]=INFINIT;
    cheie[r]=0;
    p[r]=0;                                             //radacina nu are parinte pe nimeni;
    used[r]=1;
    --cop;                                                //am selectat deja radacina
    while(cop)                                          //cat timp nu au fost selectate toate nodurile
    {
        int tata=0;
        u=extrageMinim(tata);
        S+=m[u][tata];///adaugam costul la suma minima;
        p[u]=tata;///actualizam vectorul de tati;
        ++nrmuchii;
        printf("\nS-a ales nodul %i\n",u);
        nod *q=v[u];
        while(q)
        {
            if(used[q->info]==0 && m[u][q->info] < cheie[q->info])
                {
                    cheie[q->info]=m[u][q->info];
                    p[q->info]=u;
                }
            q=q->adr_urm;
        }
        --cop;
    }

}
int main()///MATRICE DE COSTURI
{
    srand(time(NULL));
    int i=0,x,y,cost;
    FILE *f=fopen("apm.in","rt");
    FILE *g=fopen("apm.out","wt");
    fscanf(f,"%i%i",&N,&M);
    v=(nod **)calloc(N+1,sizeof(nod *));//ca sa punem NULL folosim calloc
    cheie=(int *)calloc(N+1,sizeof(int));///ca sa am de la 1 la N
    p=(int *)calloc(N+1,sizeof(int));
    used=(int *)calloc(N+1,sizeof(int));
    m=(int **)calloc(N+1,sizeof(int*));
    for(i=1;i<=N;++i)
        m[i]=(int *)calloc(N+1,sizeof(int));
    while(!feof(f))
    {
        fscanf(f,"%i%i%i",&x,&y,&cost);
        m[x][y]=cost;
        m[y][x]=m[x][y];
        nod *p=(nod *)malloc(1*sizeof(nod));
        p->info=x;
        p->adr_urm=v[y];
        v[y]=p;
        nod *r=(nod *)malloc(1*sizeof(nod));
        r->info=y;
        r->adr_urm=v[x];
        v[x]=r;
    }
    fclose(f);
    r=rand() %N +1;///aceasta va fi radacina;
    printf("%i\n",r);
    APCM_Prim();
    fprintf(g,"%i\n",S);
    fprintf(g,"%i\n",nrmuchii);
    ///acum vom afisa drumul
    for(i=1;i<=N;++i)
        if(p[i]!=0)
            fprintf(g,"%i %i\n",i,p[i]);
    return 0;
}