Problem Statement

Takahashi walks from his home to school every day. Recently, a stray dog has been spotted near a certain point along his school route. The stray dog is based at a specific point and roams around its vicinity.

Takahashi wants to choose a route that stays as far away from the stray dog's base as possible.

The town consists of N points and M bidirectional roads. Each point is numbered from 1 to N. Each road i (1 \leq i \leq M) connects point U_i and point V_i, and takes W_i minutes to traverse (W_i is a positive integer).

Takahashi's home is at point S, his school is at point T, and the stray dog's base is at point P.

The shortest travel time d(X) from the stray dog's base at point P to a point X is defined as follows:

• d(P) = 0.
• When point X (X \neq P) is reachable from point P, d(X) is the minimum travel time (sum of W_i of the roads traversed) over all paths from point P to point X.
• If point X is not reachable from point P, then d(X) = +\infty.

Here, +\infty is considered larger than any finite value.

A simple path from point S to point T is a sequence of points v_0, v_1, \ldots, v_k (where k \geq 1, v_0 = S, v_k = T) satisfying all of the following conditions:

• v_0, v_1, \ldots, v_k are all distinct (no point is visited more than once).
• For all 1 \leq j \leq k, there exists a road connecting point v_{j-1} and point v_j.

The safety score of a simple path v_0, v_1, \ldots, v_k is defined as the minimum value of d over all points on the path, including the start and end points, namely:

\min(d(v_0), d(v_1), \ldots, d(v_k))

Here, if the values of d include both finite values and +\infty, the \min takes the minimum among the finite values. The safety score is +\infty only when all d(v_j) are +\infty.

The safety score represents how far the closest point to the stray dog's base along the route is from that base.

Among all simple paths from point S to point T that Takahashi can choose, find the maximum safety score.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq S, T, P \leq N
• S \neq T
• S and P, as well as T and P, may coincide
• 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
• U_i \neq V_i (1 \leq i \leq M)
• 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
• There is at most one road connecting any pair of points
• There exists at least one simple path from point S to point T
• All input values are integers

Sample Input 1

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

Sample Output 1

1

Sample Input 2

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

Sample Output 2

INF

Sample Input 3

8 10
1 8 4
1 2 3
2 3 2
3 4 1
4 8 5
1 5 2
5 6 4
6 7 3
7 8 2
2 6 1
3 7 6

Sample Output 3

4

Sample Input 4

12 16
1 12 6
1 2 3
2 3 4
3 6 2
6 12 1
1 4 5
4 5 3
5 9 2
9 10 4
10 11 3
11 12 2
4 8 6
8 12 7
2 7 1
7 11 5
5 6 8
8 9 1

Sample Output 4

1

Sample Input 5

2 1
1 2 1
1 2 1000000000

Sample Output 5

0