一群人计划在寒假期间去赤道附近的一个偏远岛屿度假。该小组成员来自不同的国家，而目的地岛屿只能通过飞机到达。因此，每位成员都必须前往各自国家的机场，搭乘航班前往目的地岛屿。我们假设每个国家只有一个机场。现在，为了度假的兴致，所有小组成员约定在同一天从各自的家乡城市出发。此外，他们计划在同一天到达各自国家的机场，但这并不一定是他们旅行的第一天。然而，机场可能并不在每个成员的家乡城市，因此一些成员可能需要在寒假期间前往其他城市。在寒假的第一天，所有成员都在各自的家乡城市。然后，每天每位成员都必须单独决定是前往邻近的城市（意味着这两个城市由一条道路连接），还是留在当前所在的城市。由于两个城市之间的旅行费用和每个城市已知的最便宜的酒店价格是众所周知的，每个人都确切地知道每天前往邻近城市或留在当前城市需要花费多少钱。所有成员都希望在岛上尽可能多地拥有资金，因此他们将钱汇集在一起，并决定作为一个小组计算旅行计划。他们的目标是让所有成员在同一天到达各自国家的指定机场，同时花费最少的钱。

图 L.1：两位成员的国家布局，指定的机场分别在城市 4 和城市 3。两者的家乡城市均为 1。$g$ 表示两个城市之间的旅行费用，$h$ 表示最便宜的酒店价格。

考虑图 L.1 中的示例，其中有两位成员，他们指定的机场分别在城市 4 和城市 3。最便宜的旅行计划是两位成员都从他们的家乡（均为城市 1）出发，路径为：（第 1 天）成员 1 前往城市 3，成员 2 前往城市 2；（第 2 天）成员 1 前往城市 4，成员 2 前往城市 1；（第 3 天）成员 1 留在城市 4，成员 2 前往城市 3。总花费为 $(1 + 5 + 1) + (3 + 2 + 4) = 16$。

注意，两个城市之间的旅行费用不一定是对称的。此外，没有城市有连接到自身的道路。你可以始终假设，在每个国家，至少有一条从家乡到指定机场的路径。

你应该编写一个程序，找出让所有成员从各自的家乡城市到达各自国家指定机场所需的最低总费用，使得每个人都在同一天到达机场。注意，每天，每个人必须要么前往邻近的城市，要么留在当前的城市酒店。

输入格式

程序从标准输入读取数据。第一行包含一个整数 $1 \le p \le 3$，表示度假小组的人数（即需要考虑的国家数量）。接下来，输入表示每个国家的情况如下：下一行包含两个整数 $1 \le n \le 50$ 和 $n - 1 \le m \le 4 * n$，分别对应城市和道路的数量。接下来的 $n$ 行每行包含一个整数，表示每个城市最便宜的酒店价格（费用按城市 1 到 $n$ 的顺序给出）。接下来的 $m$ 行包含道路信息。每条道路由三个空格分隔的整数表示：$1 \le u, v \le n$ 和 $0 \le g \le 1,000,000$，其中 $u$ 和 $v$ 分别是道路的起点和终点，以及从 $u$ 到 $v$ 的旅行费用。最后，给出包含一个整数 $1 \le a \le n$ 的一行，表示包含该国机场的城市。在每个国家，城市 1 都是各自的家乡城市。

输出格式

程序应输出到标准输出。你应该输出一行，包含一个整数，表示让所有成员从各自的家乡城市到达各自国家指定机场所需的最低总费用，使得每个人都在同一天到达机场。

样例

样例输入 1

2 
4 4 
5 
3 
3 
1 
1 3 1 
2 3 4 
3 4 5 
4 2 2 
4 
3 3 
10 
1 
11 
1 2 3 
1 3 4 
2 1 2 
3

样例输出 1

16

样例输入 2

2 
4 4 
2 
8 
15 
1 
1 2 5 
2 3 7 
3 4 10 
4 1 3 
3 
5 4 
1 
1 
1 
1 
1 
1 2 3 
2 3 5 
3 4 7 
4 5 1 
5

样例输出 2

32