Romeo and Juliet are in love. However, their families forbid them to meet each other and Juliet wants to see Romeo so much. Luckily, she is allowed to go to sing to a choir on Sunday afternoons. She leaves her home exactly at four o'clock and she must use one of the shortest paths to the church. Similarly Romeo plays football at a nearby football stadium every Sunday. He also leaves his home at four o'clock and must also follow a shortest path.
Every Sunday Juliet hopes that going to church she will suddenly meet Romeo hurrying to the football. However, it has not happened so far and Juliet does not know whether it is possible at all.
The input file consists of several data blocks. Each data block describes one town.
The first line of a data block contains two numbers N and M, where N is the number of junctions and M is the number of streets in the town. Junctions are numbered by numbers from 1 to N. Every street connects exactly two junctions. On the second line there are four numbers JS, JG, RS, RG. Juliet lives on the junction JS, the church is at the junction JG, Romeo's home is at the junction RS and the football stadium is at the junction RG.
Each of the next M lines contains three integers A, B and T describing one street, where A and B are numbers of junctions connected by this street and T is the time in minutes necessary to walk from A to B or from B to A using this street. Suppose that it is possible to go from each junction to any other junction using the streets.
After the last block there is a single line with the number -1.
Your task is to determine for each data block whether there is a path for Romeo and a path for Juliet such that they will meet at some junction. Note, that each of them can use only a shortest path but there may be several such paths for each of them. 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.
7 9 1 4 7 6 1 2 10 2 3 10 3 4 10 4 5 15 5 1 15 1 6 10 2 7 5 5 7 15 5 6 10 2 1 1 2 2 1 1 2 10 -1Output file:
15 -1