{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e pre { text-align:left; font-family: \"Courier New\", Courier, monospace; font-size: 16px; white-space: pre; line-height:20px; text-indent: 0px; }\u003c/style\u003e\u003cdiv class\u003d\"pro_desc\"\u003e\n \u003cp\u003eXzz is a child with severe procrastinations. The new semester begins, He still has a lot of homework to do. Now, he needs your help. As the best friend, you are good at math. So, you will help him do some math homework. Now Xzz wants to go to your home. You can regard the traffic network as a undirected graph with n nodes (numbered from 1 to n) and m edges. \u003c/p\u003e\n \u003cp\u003eXzz’s home at node s, and your at node t. At each node i, there is a traffic light, and the traffic light change the status after ai, which means that you can only leave node i, at time[0, ai), [2 * ai, 3 * ai), [4 * ai, 5 * ai), … , [2k * ai, (2 * k + 1) * ai). If ai \u003d 0 means there is no traffic light, you can leave at any time. And there are m edges, each edge means it will take Xzz vi time from node xi to node yi. Now Xzz wants to know how much time he will take to arrive your home. \u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"pro_desc\"\u003e\n \u003cp\u003eFirst line of the input file contains an integer T(0 \u0026lt; ≤ 20) that indicates how many cases of inputs are there. \u003c/p\u003e\n \u003cp\u003eThe description of each case is given below: \u003c/p\u003e\n \u003cp\u003eThe first line of each case contains two numbers n, m, means there are n nodes and m edges. \u003c/p\u003e\n \u003cp\u003e(n ≤ 1000, m ≤ n(n-1) / 2)\u003c/p\u003e\n \u003cp\u003eThen follow n lines. In ith line there will be a number, ai.(ai ≤ 1000)\u003c/p\u003e\n \u003cp\u003eThen follow m lines. In ith line there will be three numbers, xi, yi and vi, means there is a edge between xi and yi, and Xzz take vi time to go trough this edge. vi ≤ 1000. \u003c/p\u003e\n \u003cp\u003eThe last line contains two numbers s, t. It’s guarantee that there is at least one path between node s and t. \u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"pro_desc\"\u003e\n One integer means the minimum time Xzz go to node t. \n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e1\r\n9 14\r\n3\r\n5\r\n7\r\n3\r\n5\r\n7\r\n9\r\n3\r\n5\r\n1 2 4\r\n1 8 8\r\n2 3 8\r\n2 8 11\r\n3 4 7\r\n3 6 4\r\n3 9 2\r\n4 5 9\r\n4 6 14\r\n5 6 10\r\n6 7 2\r\n7 9 6\r\n7 8 1\r\n8 9 7\r\n1 5\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e28\u003c/pre\u003e"}}]}