小 G 同学是一名星际飞行爱好者。他所在的联邦星域中共有 n 个城市站点，这些站点之间通过 m 条双向超空间航路相连。
每条航路 i 连接城市 u_i 与 v_i，并且在接下来的 t 天内，每天这条航路的往返飞行价格分别为 w_{i,1}, w_{i,2}, ..., w_{i,t}（在同一天的两个方向价格相同）。

为了完成自己的星际旅行计划，小 G 必须在接下来的 t 天里——每天恰好乘坐一次飞船。
已知：

1. 第一天出发时，小 G 位于城市 1；
2. 在第 j 天，他必须从第 j-1 天降落的城市出发；
3. 他每天必须选择一条与当前所在城市相连的航路进行飞行。

宇航署对连续两天的行程有特别规定（关于中间过夜的住宿费）：
假设第 j 天的行程是 A -> B，第 j+1 天的行程是 B -> C。

• 若 A != C（即不是原路返回），小 G 可以在城市 B 免费入住一晚（费用为 0）；
• 若 A == C（即第二天走了第一天航线的反向航程），则必须在城市 B 支付一晚住宿费用 c_B。

注意：旅行的最后一天（第 t 天）结束后，无需再支付住宿费用。

现给定所有航路、未来 t 天每天的航班票价，以及每个城市站点的住宿费用，你需要帮助小 G 规划一条“每天飞一次”的完整航线，使得总花费最小。

总花费包括：

1. t 天的全部机票价格；
2. 中间 t-1 个夜晚所需的住宿费用（依据上述规则计算）。

本题一个测试点中包含多组数据。
第一行：整数 T，表示测试组数。
每组数据包含以下内容：
1. 一行三个整数 n, m, t
   (n: 城市数量, m: 航路数量, t: 天数)
2. 接下来 m 行描述航路，第 i 行格式为：
   u_i v_i w_{i,1} w_{i,2} ... w_{i,t}
   代表航路 u_i <-> v_i，以及第 1 天到第 t 天的票价。
3. 最后一行输入 n 个整数：
   c_1 c_2 ... c_n
   表示在每个城市过夜的标准住宿费用。

其中：

• 1 <= T <= 10 
• 1 <= n <= 80
• 1 <= m <= n*(n-1)/2
• 1 <= t <= 80
• 1 <= w_{i,j} <= 80
• 测试点内 Sum(n) <= 80
• 无重边、无自环。

对于每组数据，输出一行一个整数，表示在 t 天飞行计划中可能达到的最小总费用。

第一组数据：
只有两个城市 1 和 2，一条路。
第 1 天只能飞 1->2，花费 10。
第 2 天只能飞 2->1，花费 20。
由于路径是 1->2->1，发生了原路返回 (A=1, B=2, C=1)，需要在城市 2 支付住宿费 c_2 = 200。
总费用 = 10 (机票) + 20 (机票) + 200 (住宿) = 230。

第二组数据：
第 1 天飞 1->2 (花费 1)。
第 2 天飞 2->3 (花费 6)。
路径 1->2->3，没有原路返回 (1 != 3)，城市 2 住宿免费。
总费用 = 1 + 6 = 7。

 "黑马程序员杯"郑州经贸学院程序设计大赛