Problem Description

C loves using a diagonal bag. However, she was told that carrying the bag on one shoulder all the time could cause her body to become crooked. Therefore, she has decided to try to carry the bag on both shoulders for equal amounts of time.

In C's country, there are $ n $ cities and $ m $ roads connecting these cities. No two different roads connect the same pair of cities.

One day, C needs to move from city $ s $ to city $ t $. She wants to switch the bag from one shoulder to the other at an intermediate city $ u $ to balance the time she carries the bag on both shoulders. However, being the fastest and strongest, she travels from city $ s $ to city $ u $ and from city $ u $ to city $ t $ via the shortest paths.

Determine if there is such a city $ u $ that allows C to balance the time she carries the bag on both shoulders.

Input Format

The input is given in the following format:

$ n $ $ m $ $ s $ $ t $ $ x_1 $ $ y_1 $ $ d_1 $ $ x_2 $ $ y_2 $ $ d_2 $ $ ... $ $ x_m $ $ y_m $ $ d_m $

• The first line contains the number of cities $ n $ ($3 \leq n \leq 1{,}000$) and the number of roads $ m $ ($1 \leq m \leq \min(n(n-1)/2, 10^4)$).
• Cities are numbered from $ 1 $ to $ n $.
• The second line contains the starting city number $ s $ ($1 \leq s \leq n$) and the destination city number $ t $ ($1 \leq t \leq n$).
• The following $ m $ lines contain the road information.
• $ x_i, y_i $ ($1 \leq x_i, y_i \leq n$ and $x_i \neq y_i$) and $ d_i $ ($1 \leq d_i \leq 1{,}000$) mean that it takes $ d_i $ time to travel between city $ x_i $ and city $ y_i $ via the $ i $-th road.
• It is guaranteed that there is a path from city $ s $ to city $ t $.

Output Format

If there exists a city $ u $ that satisfies the condition, output the number of that city in one line.

If there are multiple candidates, you may output any one of them.

If no such city $ u $ exists, output -1.

End with a newline and do not include any extra characters or blank lines.

Sample Input and Output

Sample Input #1

3 3
1 2
1 3 3
3 2 3
1 2 1

Sample Output #1

3

Sample Input #2

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

Sample Output #2

-1

Notes/Hints

Sample Explanation 1

When moving from city $ 1 $ to city $ 2 $, if city $ 3 $ is used as an intermediate city, it takes $ 3 $ time from $ 1 $ to $ 3 $ and $ 3 $ time from $ 3 $ to $ 2 $. Therefore, switching the bag at city $ 3 $ is sufficient.

Sample Explanation 2

If moving in the order $1 \to 2 \to 4 \to 3$, the burden on both shoulders can be balanced by switching the bag at city $ 4 $. However, since C takes the shortest path from city $ 1 $ to city $ 4 $, this way of moving is not possible.

见题面 Input 部分

见题面 Output 部分