描述

当流行歌星进行国际巡演时，他们通常希望在旅途中花费尽可能少的时间，以便为排练、演出以及私人生活节省更多时间。因此，他们只乘坐飞机出行，并且不断寻找前往目的地的最快路线。然而，如今可供选择的旅行方式如此之多，以至于为长途旅行找到最快的路线并非易事。这就是为什么一个能够解决这个问题的程序在市场上会很有价值，并且我们强烈鼓励作为独立软件开发者的你编写这样一个程序。

由于流行歌星只乘坐飞机出行，你的任务就大大简化了。你只需要考虑国际机场以及连接这些机场的航班。

关于乘飞机旅行，有一些你应该了解的情况：

国际机场位于不同的时区。

每个机场都有航班时刻表，该时刻表规定了每个航班的目的地、起飞时间和飞行时间；这个时刻表每天都有效。

登机（以及从一架飞机换乘到另一架飞机）需要花费时间，并且不同机场的这一时间有所不同。

为了将这个问题形式化，我们采取以下步骤：

所有国际机场的名称都被编码为标识符，这些标识符由不超过$20$ 个字母数字字符或下划线字符（即 $'a'...'z'、'A'...'Z'、'0'...'9'$ 或 '_'）组成的序列表示；所有标识符都是唯一的。

所有航班标识符都是公司代码和航班号的组合，总长度不超过 $5$ 个字母数字字符；所有这样的标识符都是唯一的。

所有标识符区分大小写。

所有表示时间的数据都采用 $"hh:mm"$ 的格式，其中 $"hh"$ 和$"mm"$ 是从 $'0'$ 到$'9'$ 的数字，分别表示小时和分钟；如果没有特别说明，则使用当地时间。

基于这些假设，你应该编写一个程序，以找到从出发机场到目的地机场的最快路线。

输入

输入文件的第一行包含出发机场和目的地机场的标识符以及旅程的开始时间，它们之间用空格分隔。开始时间是流行歌星到达出发机场的时间。

输入文件的第二行包含一个整数 $N$。这个整数表示国际机场的数量，且不小于 $2$ 且不大于$100$。

输入文件的其余部分由对各个国际机场的描述组成。每个描述都以一个标题行开始，并且可能包含一些补充行。

标题行由机场标识符、机场时区、登机时间和整数 $M$ 组成，它们之间用空格分隔。时区是当地时间与格林威治标准时间的时间差，格式为 $"shh:mm"$，其中 $"s"$ 是时间差的符号，可以是$"+"$ 或$"-"$。登机时间是在该特定机场登机或换乘飞机所需的时间延迟。整数 $M$ 定义了机场时刻表中的航班数量（不大于$300$），在标题行之后，每个航班都在其单独的一行中进行描述。

航班的描述由航班标识符、目的地机场标识符、起飞时间和飞行时间组成，它们之间用空格分隔。飞行时间是起飞和降落（到达）之间的时间间隔。

对于给定的数据，该任务总是有解的。

输出

在输出文件的第一行，你的程序应该打印总的旅行时间，该时间是从流行歌星到达出发机场的那一刻到到达目的地机场的那一刻计算的，格式为$"d:hh:mm"$，其中$"d"$ 是旅行的完整天数（任何旅程持续时间不超过 $9$ 个完整天数）。

在第二行，程序应该打印歌星到达目的地机场的当地时间。在接下来的行中，程序应该打印最佳路线的航班标识符列表——每行一个航班标识符。

输入数据 1

Pulkovo JFK 11:15
3
Pulkovo +03:00  01:30 2
BA347  Heathrow  12:10 04:25
Z8805  Heathrow  18:25 04:30
Heathrow  +00:00  00:45 3
BA160  JFK 09:20 08:10
BA346  Pulkovo 14:45 04:20
Z8804  Pulkovo 21:30 04:25
JFK -05:00  00:45 1
BA161  Heathrow  14:25 08:05

输出数据 1

1:09:15
12:30
Z8805
BA160

来源

1997 年欧洲东北部地区竞赛