题目描述

大年初三的那个晚上，小可可去电影院看了《哈利·波特与魔法石》，回到家坐在椅子上不一会儿就睡着了，并且梦见自己成了哈利·波特在充满了正义与邪恶的宇宙中执着地为了正义而战。

那天哈利·波特去拯救 Super Samuel 星球上的生灵。该星球上有七种不同的地形，依次分别是石子路、森林、草地、山地、雪地、沼泽和沙漠，用数字 $1\sim7$ 来表示。任意两个城市之间都有至少一条道路，而且任意两个能够不经过别的城市而直接通达的城市 $i$ 和 $j$ 之间都只有一种地形 $t_{i,j}$。奇怪的是，在 Super Samuel 星球上哈利·波特穿越地形 $u$ 所需要的时间与该地形的区域大小无关，却与地形 $u$ 的区域中是否有魔法石有关。如果地形 $u$ 的区域中没有魔法石，哈利·波特要花费 $h_u$ 的时间才能穿越该区域，否则他只要花一半的时间就能穿越了。已知 $h_1=2, h_2=6, h_3=4, h_4=8, h_5=6, h_6=10, h_7=14$。

• $s_u=1$ 表示地形 $u$ 的区域中有魔法石；
• $s_u=0$ 表示地形 $u$ 的区域中没有魔法石。

例如，如下图所示，有 $4$ 对可以直接通达的城市(城市 $1$ 与 $2$、$1$ 与 $3$、$2$ 与 $4$ 以及 $3$ 与 $4$)；$s_1=0, s_2=1, s_3=4, s_5=6, s_6=7$，即只有森林中有魔法石，因此穿越森林所花的时间是 $\frac{6}{2}=3$，穿越石子路和草地的时间仍然是 $2$ 和 $4$。如果哈利·波特想从城市 $1$ 到达城市 $4$，则最快的路线是经过城市 $2$，这条路线需要的时间是 $2+3=5$。

哈利·波特总是忙于铲除邪恶、伸张正义，没有时间去寻找从起点城市到终点城市的路径。现在请你作为哈利·波特的助手编写程序来找到最快路线为哈利·波特腾出更多的时间来将正义事业进行到底。

输入格式

第一行输入七个数，分别是 $S_1, S_2 ,\dots, S_7$。

第二行输入两个数，依次分别是起点城市 $i$ 和终点城市 $j$。

第三行输入一个正整数 $c$（$c\le10000$），随后的 $c$ 行中每行存放了一对能直接通达的城市的信息。能直接通达的城市的信息由三个数组成，依次分别是两个城市的编号和这两个城市之间的地形。城市的编号都是不超过 $100$ 的正整数，但是各个城市的编号未必连续。

输入文件里同一行中相邻的两个数用一个空白字符隔开。

输出格式

输出一行一个整数，表示起点城市 $i$ 与终点城市 $j$ 之间的最快路线所需要的时间。

0 1 0 0 0 0 0
1 4
4
1 2 1
1 3 1
2 4 2
3 4 3

5