Minimum Toll Fee

You are given a directed graph with N cities and M highways. Each highway connects city A to city B with a toll fee of C. Your task is to compute the minimum total toll fee required to travel from a starting city S to a target city T. If there is no possible route from S to T, output -1.

The problem can be formulated using the following notation:

\(\textbf{Input:} \; N, M, S, T\) where:

• \(N\) is the number of cities,
• \(M\) is the number of highways,
• \(S\) is the starting city,
• \(T\) is the target city.

The following \(M\) lines each contain three integers \(A_i, B_i, C_i\) representing a directed highway from city \(A_i\) to city \(B_i\) with toll fee \(C_i\).

\(\textbf{Output:}\) Print the minimum toll fee required to travel from city \(S\) to city \(T\), or -1 if no such route exists.

inputFormat

The first line of input consists of four space-separated integers N M S T.

Each of the next M lines contains three space-separated integers A B C, representing a directed highway from city A to city B with toll fee C.

outputFormat

Output a single integer: the minimum toll fee required to travel from city S to city T. If there is no route, output -1.

## sample

4 5 1 3
1 2 5
2 3 10
1 3 15
3 4 5
4 3 2

15