URI Online Judge | 2977

Romeo and Juliet

By MicrosoftRS Serbia

Timelimit: 1

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.


First 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).


Your 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 Sample Output Sample

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