題目描述

 

指縫間的陰影，它到底是什麼，冰封被吞噬，地球這個古老的名詞，早已於字典上消失，那麼還有什麼能導致月球的日食，我踢着腳邊的細沙，在黑暗裡思索。

月面從何時有的海灘，歷史已不可考，從我有記憶起，風暴洋就在那裡，伴着虛構的太陽潮起潮落，又隨日食陷入寧靜。我再次看向它，那不可一日的黑暗，幽深至極，了無星光，吞噬這個世界最後的時間。夢境、囈語、幻想，一切表象的，一切潛伏的，都將消逝殆盡，在它失控的膨脹，不可視的邊界。

它要死了，像素塔的故事，名為Phigros的夢。

真的沒有轉機嗎，我問我自己，問這片海洋，如果我投向它的懷抱，會不會有所不同。記憶在水中，在無盡海中，它會告訴你一切，它訴說着，人們心中最深的願望，一個互相理解的世界已然誕生，只是再次陷入了沉睡。

它會回來，它從沒離開。

—— 弭儿

 

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

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

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

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

但是幽蓝边界在持续吞噬着像素塔，留给Gino和鸠的时间不多了。

已知i号模块将会在时刻t_i被吞噬，Gino和鸠还能安全的到达n号模块吗？

輸入格式

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

对于每组测资：

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

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

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

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

輸出格式

对于每组测资输出一行

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

如果不能安全到达月面基地n，则输出-1

Samples

2
8 9
1 7
6 10 6 2 1 13 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
7 10
1 2
1 1 2 3 3 4 6
1 3 1
1 4 1
2 3 1
2 6 3
3 7 6
4 7 4
4 5 2
5 6 1
5 7 1
6 7 8

14 5
5 -1

提示

1 ≤ T ≤ 10

1 ≤ n, m ≤ 10⁵

1 ≤ x, y ≤ n

t_i ≤ 10⁹

sum(w) ≤ 10⁹

原始資料

• Zero1 題號：a960
• Hydro 題號：Z0960
• Locale：zh_TW
• Display：open