## IPSC 1999

## Problem H – Romeo

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.

### Input specification

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.

### Output specification

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.

### Example

**Input file:**
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
-1

**Output file:**
15
-1