描述

海因斯标识公司已承接了为州际公路系统供应路边标识牌的业务。公司负责人将某一特定类别的标识牌业务交给了他的儿子迈尔斯·海因斯负责，这类标识牌用于指示距离各个城镇的英里数。迈尔斯得到了一份公路系统的布局图以及一系列标识牌应放置的位置，他的任务是确定到附近城市的里程数。为了选择在任何一块标识牌上应列出哪些城市，他采用了以下策略：如果标识牌所在的道路满足从紧邻标识牌的前一个交叉路口到城市$X$的最短路径会使用这条道路，那么城市$X$就会被列在这块标识牌上。你可以假定每对交叉路口之间只有一条最短路径。

输入

输入由单个问题实例组成，该实例由公路系统的描述以及一组标识牌位置组成。公路系统被定义为一组交叉路口（其中一些交叉路口同时也是城市的位置）和一组连接这些交叉路口的道路。问题实例的第一行包含三个正整数$n$、$m$、$k$：$n$表示交叉路口的数量（编号为$0$、$1$、$2$、……、$n - 1$），$m$表示交叉路口之间道路的数量，$k$表示同时也是城市的交叉路口的数量。接下来是$m$行，形式为$i1\ i2\ d$，这表示在交叉路口$i1$和$i2$之间有一条双向道路，距离为$d$。再接下来的$k$行形式为$i\ name$，这表明交叉路口$i$是一个名为$name$的城市。在此之后是一行，包含一个正整数$s$，表示要在公路上放置的标识牌的数量。剩下的$s$行形式为$i1\ i2\ d$，表示要在从$i1$到$i2$的道路上放置一块标识牌，该标识牌距离$i1$的距离为$d$（$d$始终不为零且小于从$i1$到$i2$的距离）。对于所有的问题实例，$name$的长度将小于等于$18$个字符，并且$5\leq n\leq30$。所有的距离都不为零且精确到百分之一英里。

输出

每块标识牌应按如下方式输出：

name1 d1
name2 d2
...

其中每个$namei$应在宽度为$20$的字段中左对齐，每个距离$di$应四舍五入到最接近的整数英里（将$0.50$及以上向上取整。例如，$7.50$应四舍五入为$8$）。每个名称 - 距离对应按四舍五入后的距离进行排序；具有相同四舍五入后距离的对应按字母顺序打印。标识牌应按其在输入中列出的顺序输出，并且你应在每块标识牌的输出之间用一个空行分隔。你可以假定每块标识牌上至少会列出一个城市。

输入示例

8 17 4
0 1 7.12
0 2 8.34
0 3 5.33
0 4 5.36
1 2 4.21
1 6 6.99
1 7 10.26
2 3 2.74
2 6 5.04
3 4 4.12
3 5 7.72
3 6 5.71
4 5 8.94
4 6 10.29
5 6 5.47
5 7 8.55
6 7 6.01
0 Allentown
1 Bobtown
6 Charlestown
7 Downville
3
0 3 2.17
3 2 0.45
4 3 3.14

输出示例

Charlestown         9
Downville           15

Bobtown             7

Charlestown         7
Bobtown             8
Downville           13

来源

2001年美国中东部地区竞赛