girlfriend

Problem Description

Rar the Cat is actually attached since a while ago, wondered if anyone noticed -ahem-. Who do you think his girlfriend is? :)

Every time, after Rar the Cat goes out with his girlfriend, he will walk his girlfriend home if it has already past dinner time. (It's kind of dangerous letting a female kitty walk around alone at dark corners when it is late right?). This time, however, Rar the Cat could not bear to part with his girlfriend and wants to walk the longest possible route to his girlfriend's house, in order to maximize the time spend walking together under the romantic moonlight at their normal pace. (You can't walk like a snail across a short road to drag time)

There are a total of E directed cat walkways and a total of N walkway intersections. These intersections are labelled from 0 to N-1 and the directed walkways are defined using 3 integers, A, B and T, where A ≠ B and both of them are the labels of the intersections and T is the time taken to traverse this walkway. This indicates that there exist a directed walkway spanning from intersection A to intersection B and requires T time to walk. It is guaranteed that there will not be 2 walkways with the same A and B but there can be 2 walkways where their A and B are basically the same number but swapped. Eg. (3, 5) and (5, 3)

The starting location of the couple would be at intersection S and Rar the Cat's girlfriend's house is located at intersection D. Your job is to compute the longest time taken to get from S to D.

Input

The first line of input consists of 4 integers, N, E, S followed by D, in order.

Subsequent E lines will contain 3 integers each, A, B, T. 0 ≤ A, B < N

Output

Output a single integer, denoting the longest time Rar the Cat can spend with his girlfriend before they walk from S to D.

If Rar the Cat and his girlfriend is unable to get from S to D at all, output -1 instead.

If the longest time is infinite (meaning that Rar the Cat can walk for as long as he like before sending his girlfriend home), output -2 instead.

Limits

For all subtasks: 0 ≤ A, B, S, D < N, 0 < T ≤ 20000

Subtask 1 (12%): 0 < N, E ≤ 20

Subtask 2 (19%): 0 < N, E ≤ 2000

Subtask 3 (32%): 0 < N, E ≤ 100000. However, it is guaranteed that for any 2 pairs of intersection X and Y, if it is possible to get from X to Y directly or indirectly, there will not be a way to get from intersection Y to X directly or indirectly.

Subtask 4 (37%): 0 < N, E ≤ 100000. In contrast to Subtask 3, for any 2 pairs of intersection X and Y in Subtask 4, if it is possible to get from X to Y directly or indirectly, there might still be a way to get from intersection Y to X directly or indirectly as well.

Subtask 5 (0%): As per sample testcases

Sample Testcase 1

Input:

6 6 0 5
0 1 1
1 2 1
2 1 1
0 3 1
3 4 1
4 5 1

3

Sample Testcase 2

Input:

6 7 0 5
0 1 1
1 2 1
2 1 1
0 3 1
3 4 1
4 5 1
2 3 1

-2

Sample Testcase 3

Input:

6 6 2 5
0 1 1
1 2 1
0 3 1
3 4 1
4 5 1
1 3 1

-1

Sample Testcase 4

Input:

6 7 0 5
0 1 1
1 2 1
2 1 1
0 3 1
3 4 1
4 5 1
1 3 1

-2