Codah ClubUshtrohu. Dërgo. Përmirësohu.
Hyr
Shqip
#000145

BubbleRomeoAndJuliet

Romeo and Juliet are in love. However, their families forbid them to meet each other and Juliet wants to see Romeo so much. Luckily, they both live in Bubble Town, and Juliet is allowed to go to sing in a choir on Sunday afternoons. She leaves her home exactly at four o'clock and she must drive using one of the shortest paths to the church. Similarly, Romeo plays football for the Bubble Team at a nearby football stadium every Sunday. He also leaves his home at four o'clock and must follow one of the shortest paths to the stadium. All streets in the Bubble Town are one-way streets.



Every Sunday Juliet hopes that on the way to church she will suddenly see Romeo hurrying to football. However, it has not
happened so far and Juliet does not know whether it is possible at all.



InputFirst line contains two positive integer numbers n and m, with n ≤ 20000, m ≤  40000, where n is the number of junctions and m is the number of streets in the town. Junctions are numbered from 1 to n. Every street connects exactly two junctions in one direction.
On the second line there are four numbers: JS, JG, RS, RG. Juliet lives at junction JS, church is at junction JG, Romeo's home is at junction RS and the football stadium is at junction RG.
Each of the next m lines contains three integers, a, b and d describing one street, where a and b are numbers of starting and ending junction of this street and d is the time in minutes necessary to drive
from a to b using this street, d ≤ 30. It is possible to go from any junction to any other junction using streets. For a pair of junctions, there are at most two streets connecting them (at most one in each direction).


OutputYour task is to determine whether there is a shortest path for Romeo and a shortest path for Juliet such that they will see each other at some junction. Both Romeo and Juliet start at the same time. They meet at a junction only if they arrive there at the same time. If they cannot meet, output -1. If they can meet, output the time in minutes from 4 o'clock to the first possible meeting of Romeo and Juliet.


Input
5 7
1 2 4 5
1 3 5
3 2 7
4 3 5
3 5 8
4 5 13
5 1 9
2 4 6

Output
5

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.