穷游?“穷”游? | ||
---|---|---|
Time Limit: 1000 MS | Memory Limit: 10000 KB |
Description
贫穷的小A有一个梦想,就是到t国去一次穷游,但现实是残酷的。小A所在的世界一共有n(n<=500) 个国家,国家与国家之间总共有E(E<=50000)条道路相连,第i个国家对于进入它的外国人都要收取Bi 的费用,而小A家住在s国,他必须通过这些道路在各个国家之间中转最终到达t国(除非他运气够好 可以直接从s国到达t国)。但是贫穷的小A只剩下M(M<=100)元家底了,因此他必须精打细算旅途的 费用,同时小A对于t国实在太向往了,因此他希望能够走最短的路尽快到达t国。这个问题难倒了小 A,现在他请你帮他算一算他到达t国的最短路径有多长。
Input
第一行输入T(T<=10)表示有T组数据。每组数据第一行输入5个整数n、E、s、t、M,分别表示小A所在世界 的国家数、国家之间的总道路数、小A的国籍、小A向往的国家以及小A的家底;接下来一行输入n个正 整数Bi,表示第i个国家收取的过路费(由于小A是s国人,因此s国不会收取,但t国会);接下来输 入E行每行三个正整数u(1<=u<=n)、v(1<=v<=n)、w,表示u国和v国之间存在着一条长度为w的无 向边(可能有重边)。输入保证最终结果不会使int溢出。
Output
输出T行正整数,第i行表示第i组数据小A花费不超过M元到达t国的最短路。若小A无法到达t国,输 出-1.
Sample Input
3 2 2 1 2 10 20 10 1 2 1 1 2 2 3 1 1 3 10 1 1 1 2 3 1 3 3 1 3 10 1 11 1 1 2 1 1 2 3 2 3 1
Sample Output
1 -1 -1