Description

      最近新出了一款横版闯关类$RPG$游戏，这个游戏的设定是这样的：地图由$n$个魔法门和$m$条双向道路组成，每一条道路的两端连接着魔法门。当玩家以蛮力打开魔法门时会耗费此魔法门对应的体力值，但是如果使用万能魔法石，就可以不耗费体力破开任何一道魔法门，当玩家通过魔法门之后，魔法门会自动复原。当然，道路上布满了荆棘和泥泞，所以穿过一条道路也会耗费对应的体力值。

      游戏开始时，玩家会随机出现在传送门$s$前，并且携带了$k$个万能魔法石，现在已经知道只要穿过了传送门$t$之后，就可以获得此次游戏的胜利。(注意：$s$和$t$两个魔法门都需要打开，且数据保证$s$和$t$是两个不同的魔法门)

      智哥很喜欢横版闯关类的游戏，但是他觉得只获得游戏的胜利实在是太简单了，所以他决定给自己增添一点难度——只耗费最少的体力值通关。通关之后，智哥想要知道自己有没有完成自己的目标，你能帮助智哥算出他本次游戏通关所需要花费的最少体力值吗？如果无论如何都无法获得游戏的胜利，输出$-1$。

Input Format

​       在第一行中输入一个正整数$t$，代表测试用例的个数（$1\leq t \leq 10$）

​       对于每组测试用例来说：

​       在第一行中输入5个非负整数$n$，$m$，$k$，$s$，$t$。分别代表魔法门和道路的个数，智哥拥有的万能魔法石的数量，以及魔法门$s$和魔法门$t$。($2 \leq n \leq 2e4, 1 \leq m \leq 4e4, 0 \leq k \leq 50, 1 \leq s , t \leq n$）

       接下来的一行中输入以空格分割开的$n$个正整数，$p_i$代表以蛮力破开魔法门$i$所需要花费的体力值。($1 \leq i \leq n，1 \leq p_i \leq 1e9$)。

       再接下来的$m$行中，每行输入$u$，$v$，$w$，代表魔法门$u$和魔法门$v$之间有一条需要花费$w$点体力值的双向道路。（$1 \leq u, v \leq n，1 \leq w \leq 1e9$，数据可能存在自环和重边）

​       （保证所有测试用例$n$的总和不超过$2e4$，$m$的总和不超过$4e4$。)

Output Format

​       在一行中输出智哥在获得游戏的胜利后消耗的最小体力值。如果无论任何都无法获得游戏的胜利，输出$-1$。

1
5 6 2 1 4
10 100 50 5 3
1 5 50
5 4 10
1 2 1
2 4 3
2 3 8
3 4 10 

9