众所周知，海洋上的资源是非常丰富的。而在海上开采资源就必须建立开采工作站。由于海底矿藏的原因，海上的无线电信号受到一定的干扰，所以并不是所有的开采工作站都能够进行直接通讯。然而通讯是不可缺少的，所以我们保证任意两个开采工作站之间都能够进行通信（直接通信或通过一个或多个开采工作站间接通信）。开采后的资源将运回港口，海边有 n 个港口，每个港口都能与一个或多个工作站直接通信。
由于某些开采工作站间无法直接通信，为了保证货船的导航系统的安全，货船只能在直接通信的两个开采站之间航行。
现在，出现了紧急情况，停留在开采站的 n 艘货船必须紧急返回港口。由于港口管制，一个港口最多只能容纳一艘货船，如何选择货船的返航路线才能使它们的航行路线之和最小。注意，船一旦进入到港口就不会出来了！
第一行有 4 个数，n,m,k和 p，其中 n 表示有 n 艘船和 n 个港口，m 表示有 m 个开采工作站，k 表示有 k 条边，每条边连接一个开采站和另一个开采站，p 代表有 p 条边，每条边连接一个港口和一个开采站。接下来一行有 n 个数，表示每艘船所在的开采站，再接下来有 k 行，每行 3 个数 a，b，c 表示在开采站 a 和开采站 b 之间存在直接通信，它们之间的距离为 c。最后有 p 行，每行 3 个数 d,e,f,表示港口 d 和开采站 e 之间存在直接通信，它们之间的距离为 f。其中，开采站的编号为 1 到 m，港口的编号为 1 到 n，数字之间以一个空格分割。输入数据保证所有的货船最后都能返回港口。
1<=n<=100
n<=m<=200
1<=k<=15000
1<=p<=15000
0<=c,f<2^15
输出一行一个数字，表示所有货船返回港口总航线之和的最小值。
3 5 5 6 1 2 4 1 3 3 1 4 4 1 5 5 2 5 3 2 4 3 1 1 5 1 5 3 2 5 3 2 4 6 3 1 4 3 2 2
13