Travel Route Optimization

After finishing $NOIP$ $2018$, jjc decided to travel around the country. In his journey, he wishes to travel from location A to B using a map that consists of N nodes and M directed roads. Each road connects two (possibly the same) different locations and is associated with a number which represents the count of "giant bosses" he would encounter along that road. For every boss met, jjc writes down their name using a ticket. Tickets are only sold in bags of P sheets, and he wishes that by the end of his journey, every purchased bag is used exactly (i.e. the total number of sheets used must be a multiple of P). Since jjc is saving money, he also wants to minimize the total number of tickets used (i.e. the total number of bosses encountered) while satisfying the above condition.

Your task is to assist jjc in finding the optimal route from A to B whose total encountered boss count is a multiple of P and is minimized. If there is no possible route that satisfies the condition, output -1.

Note: If a route exists, output the minimum total boss count (which is also the number of tickets needed). Otherwise, output -1.

The relationship for a route with cost \(C\) must satisfy: \(C \equiv 0 \pmod{P}\).

inputFormat

The input begins with a single line containing three integers N, M and P \((1 \leq N, M \leq 10^5, 1 \leq P \leq 100)\) representing the number of locations, the number of roads, and the number of tickets per bag respectively. The next line contains two integers A and B \((1 \leq A, B \leq N)\) indicating the start and end locations.

Each of the following M lines contains three integers \(u_i\), \(v_i\) and \(w_i\) \((1 \leq u_i, v_i \leq N, 1 \leq w_i \leq 10^9)\), which denote a directed road from location \(u_i\) to location \(v_i\) with cost \(w_i\) (the number of bosses you encounter on that road).

outputFormat

Output a single integer which is the minimum total cost (i.e. number of bosses encountered) to travel from location A to location B such that the cost is a multiple of P. Output -1 if there is no such route.

sample

4 4 3
1 4
1 2 1
2 4 2
1 3 2
3 4 1

3