该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

As a travel itinerary（旅游行程） planner, what do you do when a customer asks you to plan a "both expensive and inexpensive" travel itinerary? Here are our suggestions:

• (1) For the customers to show off on their Wechat Moments, when there are a variety of transportation tools between a pair of cities that can be useddirectly , we always choose the most expensive one. For example, from Nanjing to Shanghai, we can hike, ride, take a bus, take a high-speed train, or take a plane. In this case, we should choose the plane, since it is the most expensive way.
• (2) When there are more than one route to reach the destination, we must choose the least expensive route, that is, the route with the lowest total travel expenses. Provided of course that the cost between any two adjacent cities on the route meets the requirements of (1).
• (3) When there are multiple solutions that satisfy the requirements of (2), we must choose the one that passes through the most places of interest. It is guaranteed that such a solution is unique.

输入格式

Each input file contains one test case. For each case, given in the first line are two positive integers: $n$ ( $2\le n \le 10^4$ ), the number of cities, and $m$ ( $\le 10n$ ), the number of routes that directly connect two cities in both directions.
The second line gives $n$ 0's or 1's, indicating whether the corresponding city is a place of interest or not. That is, 1 at the $i$ th position ( $1\le i\le n$ ) means that the city of index $i$ is a place of interest, and 0 means not.
Then $m$ lines follow, each giving the two endpoints of a direct route and the travel cost in the format:

City1 City2 Cost  

where the endpoint cities are numbered from 1 to $n$ and theCostis a positive integer no more than $10^4$ .
The last line gives the indices of the customer's initial position and the destination, separated by a space.

输出格式

For each test case, first output the total cost of a "both expensive and inexpensive" travel route that satisfies the requirements given by the problem description. In the second line, output the route in the format:

Source->City1- ... ->Destination  

If the solution does not exist, outputSorryinstead.

题目示例数据

8 16
1 0 1 1 0 1 1 0
3 2 5
4 2 10
5 2 5
6 2 10
3 7 5
7 3 20
4 7 10
5 8 5
8 5 2
5 8 10
6 8 5
1 2 5
2 1 60
7 1 10
1 7 5
1 8 15
2 1

30
2->4->7->1

3 1
1 1 1
1 2 1
1 3

Sorry