Minimum Life Requirement in the Forbidden Forest

On the first day of the school term, Little M embarks on an adventure into the mysterious Forbidden Forest. Little M has two attributes: magic power and life. Remarkably, at the beginning, he can choose both his initial magic power and life arbitrarily.

The Forbidden Forest is represented as an undirected, simple, connected graph with n nodes and m edges. Little M will traverse the forest following some route from a starting node s to a target node t. Every time he passes an edge:

• His magic power decreases by 1.
• On the edge there is a monster with an attack power w. Assume that right before crossing the edge his current magic power is k; then the battle on that edge will cost him \(\lfloor\frac{w}{k}\rfloor\) life. Note that if the same edge is traversed more than once, the battle occurs each time.

Little M must plan his journey so that when his magic power is completely consumed he has exactly 0 life and he is at node t. Since his initial magic power can be arbitrarily chosen, it must match the total number of edges on his path. In other words, if he chooses an initial magic power of L, he must take exactly L edges. For each edge taken as the i^th move, his magic power just before crossing is L-i+1 and he loses \(\lfloor\frac{w}{L-i+1}\rfloor\) life on that edge.

Your task is to determine the minimum initial life required for Little M in order to plan a route from s to t satisfying the condition that when his magic is exhausted (i.e. after exactly L edges), his life becomes exactly 0.

inputFormat

The first line contains four integers n m s t where n is the number of nodes, m is the number of edges, and s and t are the starting and target nodes, respectively.

The following m lines each contain three integers u v w, representing an undirected edge between nodes u and v with a monster whose attack power is w.

outputFormat

Output a single integer, which is the minimum initial life required for Little M to successfully reach node t with exactly 0 life remaining when his magic power is exhausted. If it is impossible, output -1.

sample

4 4 1 4
1 2 10
2 3 20
3 4 30
2 4 25

30