SOLVE
LATER
You are a secret agent of S.C.R.E.E.N., who infiltrated the evil organization called Hyena. You have discovered a vital information and want to send it from city s to city e via unidirectional telegraphs.
Unfortunately, you can't trust anyone, so to be sure that the message was delivered and it is correct, you want to receive an acknowledgement message from city e. So if the message was sent through cities \(s = u_1, u_2, \ldots, u_k = e\), then city e sends an acknowledgement message to \(u_{k-1}\), then \(u_{k-1}\) sends an acknowledgement message to \(u_{k-2}\) and so on, until s receives acknowledgement message.
However, the telegraph lines only work in one direction, thus, the acknowledgement message may be sent back through any other cities. Moreover, for each telegraph line that can send messages from city u to city v there is an information about delivery cost for a single message.
Your task is to find the minimal cost it takes to send message from city s to city e and get an acknowledgement message, or output -1
, if it's impossible.
The first line of the input contains four integers n, m, s and e — number of cities, number of telegraph lines and cities, sending and receiving important message, respectively (\(2 \le n \le 300\); \(1 \le s, e \le n\); \(s \ne e\); \(1 \le m \le n \cdot (n - 1)\)).
Next m lines describe telegraph lines. Each of this lines contains three integers u, v and t — the city, where the telegraph line starts, the city, where it ends, and amount of money required to deliver the message, respectively (\(1 \le u, v \le n\); \(1 \le t \le 10 ^ 4\)). All telegraph lines are unidirectional, there is no telegraph line that connects city with itself, and every telegraph line connects unique ordered pair of cities.
The output must contain a single integer — minimum money to be spent, to deliver the message in trustworthy way from city s to city e, or -1
, if it's impossible.
Task is to deliver the message from the city number 1 to city number 3. The cost to send the message from the city 1 to city 2 is \(10\). Then, the cost to send message from the city 2 to city 3 is 5. Next, the cost to receive an acknowledgement message from city 3 to 2 is 1. And finally, the cost to receive an acknowledgement message from city 2 to city 1 is \(9 = 7 + 2\) (via city 4). So, the total time is \(10 + 5 + 1 + 9 = 25\).