題目描述

这是 a960 DESTRUCTION 3,2,1 的困难版本。

 

O Fortuna velut luna statu variabilis

 

772 A.P. 08.01 幽蓝边界到达月面

幽蓝边界到达律动星后便直向月面而去。Gino和鸠相约在海滩等待最后的时刻。

月面基地共有n个被由1到n编号的模块。其中有些模块被双向异想传送门两两连接，但是通过传送门需要时间w_i。

Gino现在位于x号模块，鸠位于y号模块。他们要使用传送门前往n号模块——海滩所在之地。

但是幽蓝边界在持续吞噬着像素塔，留给Gino和鸠的时间不多了，i号模块将会在时刻t_i被吞噬。

幸好，碎数研在海滩上点放了黄绿色的烟花，改变了PhigrOS被统治局按计划毁灭的命运。每个烟花可以把在PhigrOS中不幸落入幽蓝边界的人的数据修复一次。这使得Gino和鸠可以走进被幽蓝边界吞噬的基地，然后被烟花修复数据，再利用异想传送门传送到下一个基地。

但是碍于统治局的压力，碎数研只点放了k个黄绿色的烟花。这意味着Gino和鸠最多可以途经已被幽蓝边界吞噬的基地共k次。

命运有了转折后，Gino和鸠还能安全地到达n号模块吗？

輸入格式

第一行包含一个整数 T —— 测资的个数

对于每组测资：

第一行包含三个用空格分开的整数：n, m, k —— 月面基地模块数量、异想传送门的数量和烟花的数量

第二行包含两个用空格分开的整数：x, y —— Gino和鸠所在的月面基地模块编号

第三行包含n个用空格分开的整数：t_i —— 月面基地被吞噬的时间

随后m行分别包括三个整数：u_i, v_i, w_i —— 表示基地u_i和v_i有传送门连接，需要w_i时间通过

輸出格式

对于每组测资输出一行

第一行包括用空格分开的两个数：Gino和鸠到达月面基地n需要的时间

如有多组答案，先最小化较迟到达的人需要用的时间，再最小化较早到达的人需要用的时间

如果一个人不能安全到达月面基地n，则他到达月面基地n的时间为-1

Samples

1
8 9 1
4 7
6 10 6 2 11 1 1 100
1 4 5
1 3 1
1 2 3
2 3 9
3 6 10
3 5 2
5 8 4
6 8 3
6 7 2

-1 5

提示

1 ≤ T ≤ 10

1 ≤ n, m ≤ 10⁵

1 ≤ x, y ≤ n

0 ≤ k ≤ 30

t_i ≤ 10⁹

sum(w) ≤ 10⁹

原始資料

• Zero1 題號：a975
• Hydro 題號：Z0975
• Locale：zh_TW
• Display：open