Fastest Route with Daytime Travel Constraints

There are (n) cities numbered from (1) to (n) connected by one‐directional roads. On odd days, vehicles must travel in the road’s indicated direction, and on even days they travel in the reverse direction. Each road has an associated travel time (in hours), which is the same in both directions. The journey always starts on day (1) (an odd day). In any given day, the total travel time cannot exceed (12) hours, and the vehicle must stop at a city at the end of the day. The journey may continue on subsequent days. Given the starting city (A) and the destination city (B), write a program to find a route that minimizes the overall elapsed time (including travel and waiting overnight). Note that if a route is initiated on one day but cannot complete within the remaining allowed travel time, you must wait overnight (which incurs a waiting time of (24 - t) hours if (t) hours have been used on that day) before continuing on the next day (with the day's parity toggled).

inputFormat

The first line contains four integers (n), (m), (A) and (B) where (n) is the number of cities, (m) is the number of roads, (A) is the starting city, and (B) is the destination city. Each of the following (m) lines contains three integers (u), (v) and (t), representing a road from city (u) to city (v) with travel time (t) hours.

outputFormat

Output a single integer representing the minimum total elapsed time (in hours) to reach city (B) from city (A). If it is impossible, output -1.

sample

3 3 1 3
1 2 6
2 3 6
1 3 13

12