题目描述：

在一个城市的智能交通系统中，城市的道路网络可以被表示为一个无向图，图中的每条边代表一条双向道路，边的权重代表车辆在该路段的行驶时间（单位：分钟）。城市中的两辆车分别从各自的起点出发前往目的地，你需要计算这两辆车从起点到终点的最优行驶路径，使行驶时间最短。
同时，系统需要处理实时交通数据的变化，当某些路段的行驶时间发生变化时，你需要重新计算并更新这两辆车的最优路径及其行驶时间。

输入格式：

输入的第一行包含一个整数 N，表示道路的数量。

接下来 N 行，每行包含三个元素：

  • 两个大写字母 u 和 v 表示一条双向道路的两个端点，分别为两个不同的交叉路口（即节点）。
  • 一个正整数 w 表示从节点 u 到节点 v 的行驶时间。

接下来一行，包含两个大写字母 S1 和 T1，表示车辆1的起点和终点。

接下来一行，包含两个大写字母 S2 和 T2，表示车辆2的起点和终点。

接下来一行，包含三个元素：

  • 两个大写字母 u' 和 v' 表示行驶时间发生变化的路段的两个端点。
  • 一个正整数 w' 表示该路段的新的行驶时间。

输出格式：

输出共四行：

  • 第一行输出车辆1的最优路径节点，路径上各节点之间以空格分隔。
  • 第二行输出车辆1的最优行驶时间。
  • 第三行输出车辆2的最优路径节点，路径上各节点之间以空格分隔。
  • 第四行输出车辆2的最优行驶时间。

然后，更新道路权重后：

  • 第五行输出车辆1的更新后的最优路径节点，路径上各节点之间以空格分隔。
  • 第六行输出车辆1的更新后的最优行驶时间。
  • 第七行输出车辆2的更新后的最优路径节点，路径上各节点之间以空格分隔。
  • 第八行输出车辆2的更新后的最优行驶时间。

输入样例：

6
A B 10
A C 15
B D 12
C D 10
C E 5
D E 2
A E
B E
B D 15

输出样例：

A C E 
20 
B D E 
14 
B -> D 15 
A C E 
20 
B D E 
17

输入输出解析：

输入：
第一行 6 表示图中有6条边（即6条道路）。
接下来的6行每行描述一条道路，格式为 起点 终点 行驶时间，这表示两点之间的双向道路及其行驶时间：

  • A B 10 表示从A到B的行驶时间为10分钟，双向。
  • A C 15 表示从A到C的行驶时间为15分钟，双向。
  • B D 12 表示从B到D的行驶时间为12分钟，双向。
  • C D 10 表示从C到D的行驶时间为10分钟，双向。
  • C E 5 表示从C到E的行驶时间为5分钟，双向。
  • D E 2 表示从D到E的行驶时间为2分钟，双向。

接下来的两行表示车辆的起点和终点：

  • A E 表示车辆1从A点出发，前往E点。
  • B E 表示车辆2从B点出发，前往E点。

最后一行 B D 15 表示更新从B到D的行驶时间为15分钟。

输出：

  • A C E：车辆1的最优路径。
  • 20：车辆1的总行驶时间。
  • B D E：车辆2的最优路径。
  • 14：车辆2的总行驶时间。
  • B -> D 15：更新后的道路信息。
  • A C E：更新后，车辆1的最优路径保持不变。
  • 20：车辆1的更新后总行驶时间不变。
  • B D E：更新后，车辆2的最优路径保持不变。
  • 17：车辆2的更新后总行驶时间增加为17分钟。