The Last Level

We are playing an electronic game consisting of N levels (different difficulty levels), numbered from 1 to N. The game starts necessarily from level S and ends as soon as we reach level T. Each level generally can have multiple exits, each leading to another level. We know all the exits, and for each level, we have calculated how much time we need to "move" within it and exit from each specific exit. This time may vary (i.e., if we are on level 1, it is possible to take 3 minutes to exit leading to level 17 and 6 minutes to exit leading to level 42).

However, there is another restriction in the game. There are two specific levels, P and Q, and the game does not allow us to go to track Q if we haven't first gone to level P.

We want to complete the game in the minimum possible time. We don't need to finish all the levels; it is enough to reach T.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that reads the description of the game tracks and prints the minimum possible time to complete the game.

Input Files:

The input file named supgame.in is a text file with the following structure. The first line contains six integers N, M, S, T, P, Q, separated in pairs by a single space: N is the number of levels, M is the total number of exits leading from one level to another, S and T are the initial and final levels, P and Q are the two levels mentioned above.

Each of the next M lines contains three integers ~\mathbf{X_i}~, ~\mathbf{Y_i}~, and ~\mathbf{W_i}~, separated in pairs by a single space. This triplet describes an exit: by playing level ~X_i~, we can exit from exit ~Y_i~ in a time equal to ~W_i~ minutes. Assume it is possible to complete the game.

Output Files:

The output file named supgame.out is a text file with the following structure. It has exactly one line containing exactly one integer: the minimum time, in minutes, required to complete the game.

Examples of Input - Output Files:

STDIN (supgame.in)

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

STDOUT (supgame.out)

17

Explanation: The game corresponds to the adjacent figure. We can play the levels in the following order: 1, 2, 3, 4, 6. We will need 2+2+10+3=17 minutes. The constraint is satisfied because when we reach level 4, we have already passed through level 2. It is not possible to accomplish it in less than 17 minutes.

Constraints:

• 2 ~\le~ N ~\le~ 60.000, 1 ~\le~ M ~\le~ 200.000
• 1 ~\le~ S ~\le~ N, 1 ~\le~ T ~\le~ N, S ~\neq~ T
• 1 ~\le~ P ~\le~ N, 1 ~\le~ Q ~\le~ N, P ~\neq~ Q
• 1 ~\le~ ~X_i~ ~\le~ N, 1 ~\le~ ~Y_i~ ~\le~ N, ~X_i \neq Y_i~
• 1 ~\le~ ~W_i~ ~\le~ 50.000
• For test cases worth 30% of the total points, the optimal path from level S to level T does not pass through level Q.

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 256 MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: supgame *)

for PASCAL coders

/* USER: username
LANG: C
TASK: supgame */

for C coders

/* USER: username
LANG: C++
TASK: supgame */

for C++ coders

/* USER: username
LANG: Java
TASK: supgame */

for Java coders

# USER: username
# LANG: Python
# TASK: supgame

for Python coders