405309: GYM101879 F Optimizing Transportation in Portugal

The Ministry of Construction, Transportation and Communications of Portugal is planning to improve transit routes throughout the country. The ministry's main concern is the delay everyone suffers daily in traffic when some road gets blocked. A key part of the ministry's plan is to identify roads that harm people's commute time the most. Hence, they contacted the Institute of Efficient Mobility (IME, in Portuguese).

IME is developing a software that, when given a description of the transit routes in Portugal and their usage information, finds the routes that harm the population the most when blocked. The person in charge of this important project is Marcel "the optimizer" Saito. Marcel is currently busy with administrative tasks and organizing the workforce. He has faith in you and so he is entrusting you with designing the key part of the software. You must solve the following problem: given two locations in a city, say $$$s$$$ and $$$t$$$, one wants to find the worst delay incurred when a person travels from $$$s$$$ to $$$t$$$, when exactly one road in the city gets blocked. As a pragmatic choice, you may assume that people always choose a path that takes the least time to travel from one place to another.

The first line of input has two integers, $$$N$$$ and $$$M$$$, the number of locations in the city and the number of roads connecting these locations. The locations are numbers $$$1$$$ to $$$N$$$. The second line has two integers, $$$s$$$ and $$$t$$$. Each one of the following $$$M$$$ lines has three integers, say $$$u$$$, $$$v$$$ and $$$w$$$, that describe a road that connects locations $$$u$$$ and $$$v$$$ that has a traversal time of $$$w$$$. It is guaranteed that there exists a way to reach $$$t$$$ from $$$s$$$.

Constraints

• $$$1 \leq N \leq 10^5$$$
• $$$1 \leq M \leq 5 \cdot 10^5$$$
• $$$1 \leq u, v \leq N, \, u \neq v$$$
• All roads can be traversed in both directions.
• $$$1 \leq w \leq 10^4$$$

A single integer, the greatest time it takes to go from $$$s$$$ to $$$t$$$ through a shortest path when exactly one road in the city gets blocked. If there is a road that disconnects $$$s$$$ and $$$t$$$ when blocked, print "-1" (without the quotes).

10 12
1 5
1 4 1
1 2 6
1 3 2
2 3 2
3 5 3
3 8 3
4 6 5
5 7 1
5 9 5
6 10 20
7 8 7
9 10 3

13

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

5

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

-1