//#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
typedef struct cel
{//lista muchiile, dublu inlantuita
    int to,dist,cost;
    double distLog;//distanta logaritmata
    struct cel *urm,*pre;
}muchie;

int N,M,K,start,dest,*cap,*puncte,nrp;//semnificatiile din enunt

void insert(muchie *&edge,muchie *aux)//insereaza nodul aux in lista edge asa incat lista sa fie mereu sortata
{    
    if(edge == NULL)
        edge=aux;//caz initial
    else
    {        
    muchie *copie=edge;
    while(copie->urm && copie->to < aux->to)//cauta poizitia de inserare
        copie=copie->urm;
    if(copie == edge && copie->to >= aux->to)//cand al doilea se va introduce in stanga primului
    {
        edge->pre=aux;
        aux->urm=edge;
        aux->pre=NULL;
        edge=aux;
    }
    else
    {
      if(copie->urm == NULL && copie->to >= aux->to)///daca inserarea trebuie sa se faca in stanga ultimului
      {
            copie->pre->urm=aux;
            aux->pre=copie->pre;
            aux->urm=copie;
            copie->pre=aux;
        }
        else//daca se introduce pe la mijloc
      if(copie->urm)
          copie->urm->pre=aux;
      aux->urm=copie->urm;
      copie->urm=aux;
      aux->pre=copie;
    }
    }
}

void destroy(muchie **&edges)//elibereaza spatiul alocat de lista muchiilor
{
    muchie *aux;
    int i;
    for(i=0;i<N;i++)
       while(edges[i])
       {
            aux=edges[i];
            edges[i]=edges[i]->urm;
            free(aux);
        }
    free(edges);
    edges=NULL;
}
        

int citire(char fisier[],muchie **&edges)//functia de citire
{
    FILE *f=fopen(fisier,"rt");
    if(f)
    {
        int i,from;
        muchie *aux,*aux2;
        fscanf(f,"%i%i%i%i%i",&N,&M,&K,&start,&dest);
        start--;//memorez nodurile de la 0
        dest--;
        cap=(int*)calloc(K,sizeof(int));//alocari pentru nave,puncte de articulatie, lista muchiilor
        edges=(muchie**)calloc(N,sizeof(muchie));
        puncte=(int*)calloc(N,sizeof(int));
        if(!cap || !edges || !puncte)
           return -1;          
        for(i=0;i<K;i++)
            fscanf(f,"%i",&cap[i]);//citesc nave
        for(i=0;i<N;i++)
            edges[i]=NULL;//initializez lista muchiilor
        for(i=0;i<M;i++)
        {
            aux=(muchie*)malloc(sizeof(muchie));
            aux2=(muchie*)malloc(sizeof(muchie));
            if(!aux || !aux2)
            {
                destroy(edges);
                return -2;
            }
            aux->urm=aux2->urm=aux->pre=aux2->pre=NULL;
            fscanf(f,"%i%i%i%i",&from,&aux->to,&aux->dist,&aux->cost);
            aux->distLog=log(aux->dist);//logaritmez distanta
            from--;//memorez nodurile de la 0
            aux->to--;//memorez nodurile de la 0
            insert(edges[from],aux);//inserez in lista muchiilor in lista de ordin 'from'
            if(from >= aux->to)
                free(aux2);//daca nu trebuie sa inserez si in cealalat lista, elberez
            else
            {//altfel inserez
                aux2->to=from;
                aux2->dist=aux->dist;
                aux2->cost=aux->cost;
                aux2->distLog=aux->distLog;
                insert(edges[aux->to],aux2);
            }
        }
        fclose(f);
    }
    else
        printf("Fisierul nu a fost gasit");
    return 1;
}
//afisare, pentru debuging
void afisare(muchie **edges)
{
    int i;
    muchie *aux;
    for(i=0;i<N;i++)
    {   aux=edges[i];
        printf("\nMuchii din %i\n",i);
        while(aux)
        {
            printf("%i->%f  ",aux->dist,aux->distLog);
            aux=aux->urm;
        }
    }
}
//Algoritmul din laborator pentru determinarea punctelor de articulatii
void dfsCV(muchie **edges,int nod,int *&d,int *&low,int &timp,int *&parinti,int &k)
{

  d[nod]=timp++;
  low[nod]=d[nod];
  int *copii=(int*)calloc(N,sizeof(int)),nr=0,index;
  muchie *aux=edges[nod];
  while(aux)
  {
    if( d[ aux->to ] == -1)
    {
        copii[nr++]=aux->to;
        parinti[k++]=aux->to;  
        dfsCV(edges,aux->to,d,low,timp,parinti,k);
        low[nod]= ( low[nod] < low[ aux->to ] ) ?  low[nod] : low[ aux->to ] ;//low[nod]=min(low[nod],low[aux->to])
    }
    else
    {
        for(index=0;index<k;index++)
            if(nod == parinti[index] )
             {   low[nod]= (low[nod] < d[ aux->to ]) ? low[nod]:d[ aux->to ];
                break;
            }
    }
    aux=aux->urm;
   }
   
  if(nod == start)
  {
    /*  for(index=0;index<nrp;index++)
        if(parinti[index]==nod)
            nr++;*/
    if(nr>=2)
      puncte[nrp++]=nod;
  }
  else
    for(index=0;index<timp;index++)
        if( low[ copii[index] ] >= d[nod] )
        {
            puncte[nrp++]=nod;
            break;
        }
  free(copii);
}


//Algoritmul din laborator pentru determinarea punctelor de articulatii
int puncte_articulatie(muchie **edges)
{
    int timp=0,i,*d,*low,*parinti,k=0;
    d=(int*)calloc(N,sizeof(int));
    low=(int*)calloc(N,sizeof(int));
    parinti=(int*)calloc(N,sizeof(int));
    if(!d || !low || !parinti)
        return -1;
    for(i=0;i<N;i++)
        d[i]=-1;
    for(i=0;i<N;i++)
        if(d[i] == -1)
            dfsCV(edges,i,d,low,timp,parinti,k);
    free(d);
    free(low);
    free(parinti);
    return 1;
}

//returneaza nodul cel mai apropiat de nodul de start
int extrage_min(int *&Q,int k,double *d)
{
    int i,j=0,temp;
    double min=32000;
    for(i=0;i<k;i++)
        if( d[Q[i]] < min )
        {
            min=d[Q[i]];//actualizeasza minim
            j=i;//actualizeaza pozitia
        }
    temp=Q[j];
    Q[j]=Q[k-1];//minumul se sterge, adica peste el se pune ultimul, iar nr de elemente din vector va scadea
    return temp;
}
    
void solutie(FILE *f,int *P,int val)
{//afisare solutie
    if(val != 0 && val!=-1)
    {
     //intf("\n%i %i ",dest+1,P[dest]+1);
     solutie(f,P,P[val]);
     fprintf(f,"%i ",val+1);
    }
//    printf(" :%i",d2[dest]);
}

int min(int a,int b)
{//minim
    return a>b?b:a;
}
int max(int a,int b)
{//maxim
    return a>b?a:b;
}

double modul(double x)
{//modul, abs functioneaza bine doar pe int
    if(x>0)
        return x;
    return (-1)*x;
}

int cheie(int u,int *puncte,int nrp)
{//functia care returneaza 1 daca o planeta este cheie sau 0 altfel
    int i=0;
    for(i=0;i<nrp;i++)
        if(puncte[i] == u)
            return 1;
    return 0;
}


void afiseaza(int *nava)
{//afiseaza un vector
    int i;
    for(i=0;i<N;i++)
        printf("%i ",nava[i]);
    printf("\n");
}

#define eps 0.000000001 //marja de eroare pt logaritmi

void dijkstra(FILE *f,muchie **edges,int *puncte,int nrp)
{//conform algoritmului din laborator
    int *selectat=(int*)calloc(N,sizeof(int));
    double *d=(double*)calloc(N,sizeof(double)); //distanta logaritmata
    long *d2=(long*)calloc(N,sizeof(long));//distanta normala
    int *P=(int*)calloc(N,sizeof(int));//parintii
    int *Q=(int*)calloc(N,sizeof(int));
    int *q=(int*)calloc(N,sizeof(int));//q va retine 1 daca un anume nod a fost introdus in vectorul Q
    int *consum=(int*)calloc(N,sizeof(int));//consum[i] va retine cat lipseste din rezervor atunci cand se ajunge pe planta i
    int *maximi=(int*)calloc(N,sizeof(int));//maximi[i]  retine nava de capacitate minima cu care pot sa ajung pe planeta i
    int i=0,k;
    muchie *aux=edges[start];//toti copii nodului start
    selectat[start]=1;
    P[start]=-1;
    consum[start]=0;
    q[start]=1;
    for(i=0;i<N;i++)
       P[i]=-1;
    i=0;
    while(aux)
    {//parcurg copii lui start pentru initializari
        d[aux->to]=aux->distLog;
        d2[aux->to]=aux->dist;
        consum[aux->to]=aux->cost;
        maximi[aux->to]=aux->cost;
        P[aux->to]=start;
        q[aux->to]=1;      
        Q[i++]=aux->to;      
        aux=aux->urm;
    }
    k=i;
    for(i=0;i<N;i++)
        if(P[i]==-1)
        {//initializari
            d[i]=d2[i]=1000000000;
            consum[i]=32000;
            maximi[i]=0;
            P[i]=-1;
        }
    int u;
    d[start]=0;
    d2[start]=0;
    consum[start]=0;
    maximi[start]=0;
    while(k>0)
    {//cat timp mai exista elemente in Q
        u = extrage_min (Q,k,d);
        selectat[u]=1;
        k--;   
        aux=edges[u];//copii nodului de prelucrat
    
        while(aux)
        {//pentru fiecare copil
           if( modul(d[aux->to] - (d[u] + aux->distLog) )  <= eps && selectat[aux->to]==0)//daca nu a fost vizitat si daca timpul este acelasi
           {
                //incercam sa folosim o nava de capacitate minima
            if( cheie(u,puncte,nrp) )//daca planeta u este peco
            {   if( max(maximi[u],aux->cost) < maximi[aux->to])//daca pe acest drum pot veni cu o nava mai mica
                {//actualizez
                    maximi[aux->to] = max(maximi[u],aux->cost);
                    consum[aux->to] = aux->cost;     
                    P[aux->to]=u;
                }
             }
             else//daca nu este peco
                if( max(maximi[u],consum[u] + aux->cost) < maximi[aux->to] )//daca pe acest drum pot veni cu o nava mai mica
                {//actualizez
                    consum[aux->to] = consum[u] + aux->cost;
                    maximi[aux->to]=max(maximi[u],consum[aux->to]);
                    P[aux->to]=u;
                }
           }          
             else  //altfel
            if( selectat[aux->to] == 0 && d[aux->to] - (d[u] + aux->distLog)   > eps )//daca nu e vizitat si am gasit un timp mai bun, relaxez
            {
                     d[aux->to]=d[u] + aux->distLog;//actualizez distanta cu o valoare mai mica
                     d2[aux->to]=(d2[u] * aux->dist)%1000000;//retin ultimele 6 cifre ale timpului
                     
                     if( cheie(u,puncte,nrp) )
                     {//daca este peco
                            consum[aux->to]=aux->cost;//cand voi ajunge pe copilul lui u din rezervor vor lipsi   aux->cost  unitati de combustibil
                            maximi[aux->to]=max(maximi[u],aux->cost);
                     }
                     else
                     {//altfel
                            consum[aux->to]=consum[u]+ aux->cost;
                            maximi[aux->to]=max(maximi[u],consum[aux->to]);
                    }
                     
                     P[aux->to]=u;
                     if(q[aux->to]==0)//daca nu a fost introdus inainte in coada
                      {
                               Q[k++]=aux->to;//il introduc
                               q[aux->to]=1;//bifez ca a fost introdus
                      }
            }
            aux=aux->urm;//urmatorul copil
        }
    }
    u=32000;
    //maximi[dest] retine capacitatea navei ideale
    for(i=0;i<K;i++)
      if(cap[i] >= max(maximi[dest],consum[dest]) && u > cap[i])
      {//caut cea mai apropiata nava de cea ideala
         u=cap[i];
        
      }
    fprintf(f,"%li %i",d2[dest],u);//afisez timpul si nava
    fprintf(f,"\n%i ",start+1);//startul
    solutie(f,P,P[dest]);//restul drumului
    fprintf(f,"%i",dest+1);  //destiantia
    free(selectat);
    free(d);
    free(d2);free(P);free(Q);free(q);free(consum);free(maximi);
}
    
        
int main()
{
    muchie **edges=NULL;
    char fisier[]="misiune.in";
    citire(fisier,edges);//citirea din fisier
    puncte_articulatie(edges);//determinarea punctelor de articulatie
    //afisare(edges);
  //  int i=0;
 // printf("\nPuncte de articulatie:");
 // for(i=0;i<nrp;i++)
  //    printf("%i ",puncte[i]+1);
    FILE *f=fopen("misiune.out","wt");
   dijkstra(f,edges,puncte,nrp);
  fclose(f); 
    //getch();
    destroy(edges);
    return 0;
}