#include #include #include #include #include #include #include using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) map M; int gid(string a) { if(M.find(a)==M.end()) { int t=M.size(); M[a]=t; return t; } return M[a]; } vector > rt_city,rt_dst,rt_time; vector > > H; int main() { int L; while(1) { scanf("%d",&L); if(L<0) break; M.clear(); H= vector > >(1000); rt_city.clear(); rt_time.clear(); rt_dst.clear(); REP(r,L) { rt_city.push_back(vector()); rt_time.push_back(vector()); rt_dst.push_back(vector()); int a=0; while(a>=0) { rt_dst[r].push_back(a); char p[1000]; scanf("%s %d",p,&a); rt_city[r].push_back(gid(p)); } REP(i,rt_dst[r].size()-1) { H[rt_city[r][i]].push_back( make_pair(r,i)); rt_dst[r][i+1]+=rt_dst[r][i]; } int k; scanf("%d",&k); REP(i,k) { int a; scanf("%d",&a); rt_time[r].push_back(a); } } //readinput int n=M.size(); priority_queue > Q; //DIJKSTRA START int dist[1000]; REP(i,n) dist[i]=-1; Q=priority_queue >(); char p[1000]; int hod,mn; scanf("%d:%d %s",&hod,&mn,p); dist[gid(p)]=60*hod+mn; Q.push(make_pair(-dist[gid(p)],gid(p))); while(!Q.empty()) { pair a = Q.top();Q.pop(); int moj_cas = dist[a.second] % 60; REP(i,H[a.second].size()) { int r=H[a.second][i].first; int por=H[a.second][i].second; int dlz=rt_dst[r][por+1]-rt_dst[r][por]; int src=rt_city[r][por]; int trg=rt_city[r][por+1]; REP(j,rt_time[r].size()) { int time2=(rt_time[r][j]+rt_dst[r][por]) %60; int new_time=0; if(time2>=moj_cas) new_time = time2-moj_cas+dlz; else new_time=60+time2-moj_cas +dlz; if(dist[trg]==-1 || dist[trg]>dist[src]+new_time) { dist[trg]=dist[src]+new_time; Q.push(make_pair(-dist[trg],trg)); } } } } //DIJKSTRA END //DIJKSTRA START int dist2[1000]; REP(i,n) dist2[i]=-1; Q=priority_queue >(); scanf("%d:%d %s",&hod,&mn,p); dist2[gid(p)]=60*hod+mn; Q.push(make_pair(-dist2[gid(p)],gid(p))); while(!Q.empty()) { pair a = Q.top();Q.pop(); int moj_cas = dist2[a.second] % 60; REP(i,H[a.second].size()) { int r=H[a.second][i].first; int por=H[a.second][i].second; int dlz=rt_dst[r][por+1]-rt_dst[r][por]; int src=rt_city[r][por]; int trg=rt_city[r][por+1]; REP(j,rt_time[r].size()) { int time2=(rt_time[r][j]+rt_dst[r][por]) %60; int new_time=0; if(time2>=moj_cas) new_time = time2-moj_cas+dlz; else new_time=60+time2-moj_cas +dlz; if(dist2[trg]==-1 || dist2[trg]>dist2[src]+new_time) { dist2[trg]=dist2[src]+new_time; Q.push(make_pair(-dist2[trg],trg)); } } } } //DIJKSTRA END int sol=-1; // REP(i,n) { // printf("%d %d\n",dist[i],dist2[i]); // } REP(i,n) if(dist[i]!=-1 && dist2[i]!=-1) { if(sol==-1 || sol>max(dist[i],dist2[i])) sol=max(dist[i],dist2[i]); } if(sol==-1) printf("No connection\n");else { int hod= sol/60; int mn=sol-hod*60; printf("%d:%02d\n",hod%24,mn); } } return 0; }