Trustworthy network
Tag(s):

## Algorithms, Dijkstra, Easy-Medium, Floyd Warshall

Problem
Editorial
Analytics

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.

### Input format

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.

### Output format

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.

SAMPLE INPUT
4 5 1 3
1 2 10
2 3 5
2 4 7
3 2 1
4 1 2

SAMPLE OUTPUT
25

Explanation

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$.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

November Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Math > Basic Math
• Math > Combinatorics
• Algorithms > Dynamic Programming
• Math > Number Theory