跑步是一项有意思的运动，尤其是可以开发人的脑筋。常神牛很喜欢跑步。
常神牛跑步的场地是一个多边形（边数 ，每个顶点用英文大写字母表示），并且在这个多边形内部，还会有一些小道，连接两个不相邻的顶点。所有的边长和小道都是双向通行的举例来说，下面一个图：
假设常神牛从 点跑到 点，最短的路径是 （长度为 ）。
现在告诉你多边形的边数 ，多边形每条边的长度，多边形内的连线数 ，每条连线的两个端点及长度，以及起始点和结束点，请你输出最短路径的长度。但是常神牛有点强迫症，如果两点之间有多条道路直接连接，他会选择最长的那条。
注意：输入数据不保证起点和终点不同，也不保证小道的起点和终点不同。在读入过程中，如果两点之间有多条小道，那么它们间的距离为这些小道的最大值。所以，如果读入一个小道起点和终点相同，那么这个点到它本身的距离不为 。
