Minimum Cost Route

There are $n$ cities and $m$ buses. Each bus leaves one city and arrives at a different city. You want the total fare of a trip from city $A$ to city $B$ to be as small as possible. Print that minimum fare and a route that achieves it. A route from the start city to the destination city always exists.

If several routes reach the minimum fare, pick one of them in this order.

1. Pick the route that passes through the fewest cities.
2. If several routes are still left, pick the one whose city numbers, listed in visiting order, form the sequence that comes first in lexicographic order.

The first line contains the number of cities $n$. $1 \le n \le 1000$

The second line contains the number of buses $m$. $1 \le m \le 100000$

Each of the next $m$ lines describes one bus with the number of its start city, the number of its destination city, and its fare, in that order. A fare is an integer that is at least $0$ and less than $100000$. No bus starts and ends at the same city, and several buses may run the same route.

The last line contains the start city $A$ and the destination city $B$ of the trip you must plan. $A$ and $B$ are different.

On the first line, print the minimum fare of a trip from $A$ to $B$.

On the second line, print how many cities the chosen route contains, counting the start city and the destination city.

On the third line, print the numbers of the cities on the chosen route in visiting order, separated by spaces. Exactly one route satisfies both tie breaking rules.