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

typedef int Train;
typedef int Station;
typedef int Time;          // čas budeme reprezentovat jako počet minut

#define DAY (24 * 60)      // délka dne v minutách

#define INFINITE ((Time)(-1))

void readTime(istream&, Time &);    // čtení času ze vstupu
void writeTime(ostream&, Time &);   // zápis času na výstup

class StringContainer {
public:
   int Insert(char *s);    // přidá řetězec s a vrátí jeho index
                           // jestliže řetězec již existuje, vrátí -1
   int Find(char *s);      // najde řetězec s a vrátí jeho index
                           // jestliže řetězec neexistuje, vrátí -1
   char *Fetch(int i);     // vrátí řetězec s indexem i
   int Size();             // vrátí počet uložených řetězců
}; 

StringContainer stations;

struct ScheduleItem {
   Train train;            // číslo vlaku
   Time departure, arrive; // čas odjezdu, čas příjezdu do další stanice
   Station next;           // číslo další stanice
};

struct ScheduleItem **schedule;  // jízdní řád
                                 // konec pole s vlaky vyjíždějícími z dané stanice 
                                 // je označen vlakem s číslem 0
               
int readTimetable(char *); // načte jízdní řád do schedule a stations

struct HeapItem {
   Time arrive;         // nejlepší čas, ve kterém jsme schopni se do stanice se dopravit
   Station previous;    // předchozí stanice na cestě
   Time departure;      // čas odjezdu z předchozí stanice
   Train train;         // číslo tohoto vlaku, kterým jsme do stanice přijeli
};

class FibHeap { // správnější by bylo použít template
public:
   void Insert(struct HeapItem *);  // vloží do haldy prvek a
   HeapItem *DeleteMin();     // vrátí prvek s minimální hodnotou a z haldy ho vyřadí
                              // vrátí nil, když je halda prázdná
   void Decrease(HeapItem *); // znovu zatřídí do haldy prvek po snížení jeho ohodnocení
};

int main(int argc, char *argv[])
{
   if(argc < 2)
   {     
      cerr << "Usage: " << argv[0] << " <timetable_filename>\n";
      return 1;
   }

   readTimetable(argv[1]);

   struct HeapItem *w = (struct HeapItem *)malloc(sizeof(struct HeapItem) * stations.Size());

   while(!cin)
   {  
      for(int i = 0; i<stations.Size(); i++) w[i].arrive = INFINITE;
      
      char from[17], to[17];
      Time start;
      
      cin >> from >> to;
      readTime(cin, start);

      Station f = stations.Find(from);
      Station t = stations.Find(to);

      if((f < 0) || (t < 0))
      {
         cout << "Invalid stations!\n";
         continue;
      }

      w[f].arrive = start;

      FibHeap heap;
   
      struct HeapItem *m = w + f;

      while(m != w + t) {

         int i = m - w;

         // poslední vlak má číslo nula 
         for(struct ScheduleItem *p = schedule[i]; p->train; p++) { 

            int j = p->next;

            // vlakem můžeme cestovat i několik dní
            // days říká, o kolik dní je třeba posunout odjezd vlaku, abychom ho stihli
            int days;                     
            if(m->arrive < p->departure) days = (m->arrive - p->departure + 1) / DAY;
            else days = (m->arrive - p->departure) / DAY + 1;
            
            if(w[j].arrive == INFINITE)
            {
               w[j].arrive = p->arrive + DAY * days;
               w[j].departure = p->departure + DAY * days; 
               w[j].previous = i;
               w[j].train = p->train;

               heap.Insert(w + j);
            } 
            else
            {
               if(w[j].arrive > p->arrive + DAY * days) {
                  w[j].arrive = p->arrive + DAY * days;
                  w[j].departure = p->departure + DAY * days; 
                  w[j].previous = i;
                  w[j].train = p->train;

                  heap.Decrease(w + j);
               }
            }
         }

         if(!(m = heap.DeleteMin())) break;
      }

      if(w[t].arrive == INFINITE) { cout << "No connection!\n"; }
      else {
         Station i, j;
         
         // rekonstrukce cesty
         
         j = w[i = t].previous;

         while(i != f) {
            Station k = w[j].previous;          
            w[j].previous = i;   // previous nebude previous ale next!!!
            i = j;
            j = k;
         }

         // vypsání cesty

         i = f;

         while(i != t) {
            int j = w[i].previous; // previous je next!!!

            cout << "Station:   " << stations.Fetch(i) << "\n";
            cout << "Departure: "; writeTime(cout, w[j].departure); cout << "\n";
            cout << "Train:     " << w[j].train << "\n";
            cout << "Arrival:   "; writeTime(cout, w[j].arrive); cout << "\n";
            
            i = j;
         }

         cout << stations.Fetch(t) << "\n";        
      }
   }

   return 0;
}