George

Την περασμένη εβδομάδα ο κύριος George επισκέφτηκε την Κροατία. Δεδομένου ότι ο κύριος George είναι ένα πολύ σημαντικό πρόσωπο, ενώ βρισκόταν σε έναν δρόμο, η αστυνομία δεν επέτρεψε την είσοδο σε αυτόν τον δρόμο, αλλά τα οχήματα που μπήκαν στον δρόμο πριν από τον κύριο George μπορούσαν να συνεχίσουν να οδηγούν.
Ενώ ο κύριος George έκανε επίσκεψη, ο Luka οδήγησε το φορτηγό του στην πόλη. Αλλά επειδή ορισμένοι δρόμοι ήταν κλειστοί, δεν μπόρεσε να κάνει την παράδοσή του εγκαίρως και κόντεψε να χάσει τη δουλειά του. Αν και είναι αργά τώρα, αναρωτιέται πώς θα μπορούσε να είχε σχεδιάσει καλύτερα την παράδοσή του, δηλαδή ποιος θα ήταν ο λιγότερος χρόνος που χρειαζόταν για να γίνει η παράδοσή του ενώ ο κύριος George έκανε επίσκεψη. Ξέρει τη διαδρομή που πήρε ο κύριος George.
Η πόλη διαμορφώνεται με διασταυρώσεις και αμφίδρομους δρόμους που τις ενώνουν. Για κάθε δρόμο, ο Luka ξέρει πόσο χρόνο χρειάζεται για να τον διασχίσει (ο κύριος George χρειάζεται τον ίδιο χρόνο).
Για παράδειγμα, εάν ο κύριος George αρχίσει να διασχίζει έναν δρόμο κατά το λεπτό ~10~ και χρειάζεται ~5~ λεπτά για να βγει από αυτόν, αυτός ο δρόμος θα αποκλειστεί κατά τα λεπτά ~10~, ~11~, ~12~, ~13~ και ~14~. Ο Luka μπορεί να εισέλθει στον δρόμο κατά τα λεπτά ~9~ και νωρίτερα, ή ~15~ και μετά.
Γράψτε ένα πρόγραμμα που να υπολογίζει τον ελάχιστο χρόνο που χρειάζεται ο Luka για να κάνει την παράδοσή του, εάν αρχίσει να οδηγεί ~K~ λεπτά μετά την άφιξη του κυρίου George.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~N~ και ~M\;(2 \le N \le 1\,000,\;2 \le M \le 10\,000)~, τον αριθμό των διασταυρώσεων και τον αριθμό των οδών. Οι διασταυρώσεις αριθμούνται από ~1~ έως ~N~.
Η δεύτερη γραμμή περιέχει τέσσερις ακέραιους αριθμούς ~A,\;B,\;K~ και ~G\;(1 \le A, B \le N,\;0 \le K \le 1\,000,\;0 \le G \le 1\,000)~.
Αυτά είναι κατά σειρά:

• Η διασταύρωση όπου ξεκινά ο Luka.
• Η διασταύρωση που ο Luka πρέπει να φτάσει.
• Η διαφορά στους χρόνους εκκίνησης μεταξύ του κυρίου George και του Luka (Ο Luka ξεκινά στη διασταύρωση ~A~ ακριβώς ~K~ λεπτά αφότου ο κύριος George ξεκινήσει τη διαδρομή του).
• Ο αριθμός των διασταυρώσεων στη διαδρομή του κυρίου George.

Η τρίτη γραμμή περιέχει ακέραιους αριθμούς ~G~, τις ετικέτες των διασταυρώσεων που θα επισκεφτεί ο κύριος George. Κάθε ζεύγος γειτονικών ακεραίων δηλώνει έναν δρόμο που θα διασχίσει. Αυτός ο δρόμος θα υπάρχει και ο κύριος George θα διασχίσει κάθε δρόμο το πολύ μια φορά.
Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει τρεις ακέραιους αριθμούς ~A,\;B~ και ~L~, που σημαίνει ότι υπάρχει ένας δρόμος μεταξύ των διασταυρώσεων ~A~ και ~B~ και χρειάζονται ~L~ λεπτά για να διασχιστεί. Το ~L~ θα είναι μεταξύ ~1~ και ~1\,000~.

Έξοδος

Δώστε τον ελάχιστο χρόνο (σε λεπτά) που χρειάζεται ο Luka για να κάνει την παράδοσή του.

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

input

6 5
1 6 20 4
5 3 2 4
1 2 2
2 3 8
2 4 3
3 6 10
3 5 15

output

21

input

8 9
1 5 5 5
1 2 3 4 5
1 2 8
2 7 4
2 3 10
6 7 40
3 6 5
6 8 3
4 8 4
4 5 5
3 4 23

output

40