Train

Στη Δημοκρατία του AtCoder, υπάρχουν ~N~ πόλεις που αριθμούνται από το ~1~ έως το ~N~ και ~M~ σιδηρόδρομοι που αριθμούνται από το ~1~ έως το ~M~.

Ο σιδηρόδρομος ~i~ συνδέει αμφίδρομα τις πόλεις ~A_i~ και ~B_i~. Τη χρονική στιγμή ~0~, ~K_i~, και όλα τα ακόλουθα πολλαπλάσια του ~K_i~, ένα τρένο αναχωρεί από κάθε μία από αυτές τις πόλεις και κατευθύνεται προς την άλλη πόλη. Ο χρόνος που χρειάζεται κάθε ένα από αυτά τα τρένα για να φτάσει στον προορισμό του είναι ~T_i~.

Βρίσκεστε τώρα στην πόλη ~X~. Βρείτε την συντομότερη δυνατή ώρα που μπορείτε να φτάσετε στην πόλη ~Y~ ξεκινώντας το ταξίδι σας παίρνοντας ένα τρένο που αναχωρεί από την πόλη ~X~ όχι νωρίτερα από την ώρα ~0~. Εάν η πόλη ~Y~ δεν είναι προσβάσιμη, αναφέρετε το γεγονός αυτό. Ο χρόνος που απαιτείται για τη μεταφορά δεν λαμβάνεται υπόψη. Δηλαδή, σε κάθε πόλη, μπορείτε να μετεπιβιβαστείτε σε ένα τρένο που αναχωρεί ακριβώς την ώρα που το τρένο σας φτάνει στην πόλη αυτή.

Περιορισμοί

• ~2 \le N \le 10^5~
• ~0 \le M \le 10^5~
• ~1 \le X,Y \le N~
• ~X \neq Y~
• ~1 \le A_i, B_i \le N~
• ~A_i \neq B_i~
• ~1 \le T_i \le 10^9~
• ~1 \le K_i \le 10^9~
• Όλες οι τιμές στην είσοδο θα είναι ακέραιοι αριθμοί.
• Time Limit: ~2~ sec.
• Memory Limit: ~1024~ MB

Είσοδος

Η είσοδος θα δίνεται από την τυπική είσοδο και θα έχει την ακόλουθη μορφή:

N  M  X  Y

A1​ B1​ T1​ K1​

⋮

AM​ BM​ TM​ KM​

Έξοδος

Εκτυπώστε τη συντομότερη δυνατή ώρα που μπορείτε να φτάσετε στην πόλη ~Y~. Εάν η πόλη ~Y~ δεν είναι προσβάσιμη, εκτυπώστε ~-1~.

Παραδείγματα

1ο

input

3 2 1 3
1 2 2 3
2 3 3 4

output

7

Επεξήγηση πρώτου παραδείγματος:

Πρώτα, παίρνετε το σιδηρόδρομο ~1~ τη στιγμή ~0~ και πηγαίνετε από την πόλη ~1~ στην πόλη ~2~. Φτάνετε στην πόλη ~2~ τη χρονική στιγμή ~2~.

Στη συνέχεια, παίρνετε το σιδηρόδρομο ~2~ τη στιγμή ~4~ και πηγαίνετε από την πόλη ~2~ στην πόλη ~3~. Φτάνετε στην πόλη ~3~ τη στιγμή ~7~.

Δεν υπάρχει τρόπος να φτάσετε στην πόλη ~3~ νωρίτερα.

2ο

input

3 2 3 1
1 2 2 3
2 3 3 4

output

5

Επεξήγηση δεύτερου παραδείγματος:

Πρώτα, παίρνετε το σιδηρόδρομο ~2~ τη στιγμή ~0~ και πηγαίνετε από την πόλη ~3~ στην πόλη ~2~. Φτάνετε στην πόλη ~2~ τη χρονική στιγμή ~3~.

Στη συνέχεια, παίρνετε το σιδηρόδρομο ~1~ τη στιγμή ~3~ και πηγαίνετε από την πόλη ~2~ στην πόλη ~1~. Φτάνετε στην πόλη ~1~ τη στιγμή ~5~.

3ο

input

3 0 3 1

output

-1

4ο

input

9 14 6 7
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
2 3 8 4
6 2 6 4
3 8 3 2
7 9 5 2
8 4 1 9
7 1 6 9
3 9 9 3
7 5 1 5
8 2 9 7
4 9 4 4

output

26