Vampire Tunnels

Είστε βαμπίρ και θέλετε να ταξιδέψετε από κάποιο σημείο ~A~ σε ένα άλλο σημείο ~B~. Μπορείτε να ταξιδέψετε στον ήλιο πάνω από το έδαφος ή να αποφύγετε την ηλιοφάνεια ταξιδεύοντας υπόγεια μέσω ορισμένων τούνελ. Έχετε χαρτογραφήσει την περιοχή που θέλετε να ταξιδέψετε και βρήκατε μερικές μυστικές σήραγγες μεταξύ κάποιων σημείων, κάποια άλλα σημεία που μπορείτε να περπατήσετε από το ένα στο άλλο πάνω από το έδαφος. Τόσο οι σήραγγες όσο και οι υπέργειες διαδρομές είναι αμφίδρομες. Δεδομένου ότι δεν μπορείτε να εκτεθείτε στο φως του ήλιου για περισσότερο από ~S~ δευτερόλεπτα συνολικά (~0 \le S \le 3\,600~), θέλετε να ελαχιστοποιήσετε τον συνολικό χρόνο ταξιδιού (δεδομένου ότι έχετε σταθερή ταχύτητα ~1~ μονάδα απόστασης ανά δευτερόλεπτο).

Είσοδος

Στην πρώτη γραμμή της εισόδου, έχετε έναν αριθμό ~S~, τον μέγιστο αριθμό δευτερολέπτων που μπορείτε να είστε εκτεθειμένοι στον ήλιο. Στην επόμενη γραμμή είναι ο αριθμός ~N~ (~2 \le N \le 1\,600~), ο οποίος είναι ο αριθμός των σημείων και ο αριθμός ~E~ (~1 \le E \le 10\,000~), ο οποίος είναι ο αριθμός των συνδέσεων μεταξύ αυτών των ~N~ σημείων, χωρισμένα με ένα κενό.

Οι επόμενες ~E~ γραμμές καθεμία περιέχουν πληροφορίες σχετικά με τις συνδέσεις μεταξύ των σημείων. Ειδικότερα, κάθε μία από αυτές τις γραμμές περιέχει τέσσερις ακέραιους: ~s~ (ένα τελικό σημείο μιας σύνδεσης) (~0 \le s \le N - 1~), ~t~ (το άλλο τελικό σημείο μιας σύνδεσης) (~0 \le t \le N - 1~, ~s \ne t~), ~d~ (την απόσταση μεταξύ του ~s~ και του ~t~, ~1 \le d \le 10\,000~), ~u~ (που δείχνει αν είναι υπόγειο ή υπέργειο: το ~1~ δείχνει ότι είναι πάνω από το έδαφος και το ~0~ δείχνει ότι είναι ένα τούνελ μεταξύ του ~s~ και του ~t~).

Σημείωση: για το ~30~% των βαθμών για αυτή την ερώτηση, μπορείτε να υποθέσετε ότι ~N \le 50~.

Έξοδος

Η έξοδος είναι ένας ακέραιο, ο οποίος είναι ο ελάχιστος χρόνος που απαιτείται για να πάτε από το σημείο ~0~ στο σημείο ~N - 1~, με τον περιορισμό ότι δεν υπάρχουν πάνω από ~S~ δευτερόλεπτα έκθεσης στον ήλιο. Αν δεν υπάρχει κάποιο μονοπάτι που να ικανοποιεί τον περιορισμό, εκτυπώστε -1.

Παράδειγμα

input

3
4 6
0 1 3 1
0 2 4 1
0 3 10 1
1 2 3 0
1 3 1 1
2 3 3 0

output

9

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

Το μονοπάτι ~0 \rightarrow 1 \rightarrow 2 \rightarrow 3~ δίνει έναν συνολικό χρόνο ταξιδιού ~9~ δευτερολέπτων με ~3~ δευτερόλεπτα έκθεσης στον ήλιο. Όλα τα άλλα μονοπάτια είτε απαιτούσαν περισσότερο χρόνο (πχ, ~0 \rightarrow 3~ χρησιμοποιεί ~10~ δευτερόλεπτα) είτε σας υπερεκθέτουν στον ήλιο (πχ, ~0 \rightarrow 1 \rightarrow 3~ σας εκθέτουν στον ήλιο για ~4~ δευτερόλεπτα).