Speed Limits

Baltic Olympiad in Informatics: 2002 Day 1, Problem 1

Στον πολυάσχολο κόσμο μας, συνήθως δεν μας ενδιαφέρει να ακολουθήσουμε το συντομότερο μονοπάτι, αλλά μάλλον το μονοπάτι που απαιτεί το συντομότερο χρόνο. Όταν οδηγείτε ένα αυτοκίνητο, αυτό σημαίνει ότι τα όρια ταχύτητας στους διάφορους δρόμους είναι ζωτικής σημασίας. Φανταστείτε τώρα ότι κάποιες πινακίδες ορίων ταχύτητας λείπουν. Δεδομένου ότι δεν μπορούμε να περιμένουμε από τον οδηγό να γνωρίζει τα όρια ταχύτητας απ' έξω, το μόνο λογικό συμπέρασμα είναι ότι όποιο όριο ταχύτητας τηρούσε προηγουμένως, θα εξακολουθεί να ισχύει και μετά τη διέλευση από σημείο που λείπει πινακίδα. Πρέπει να γράψετε ένα πρόγραμμα που να υπολογίζει την ταχύτερη διαδρομή, εκμεταλλευόμενοι τις πινακίδες που λείπουν.

Σας δίνεται μια περιγραφή του οδικού δικτύου σε μια περιοχή με έντονη κίνηση. Προς διευκόλυνση, το δίκτυο θα αποτελείται από διαβάσεις και δρόμους. Κάθε δρόμος είναι μονόδρομος, συνδέει ακριβώς δύο διαβάσεις και έχει το πολύ μία πινακίδα ορίου ταχύτητας, που βρίσκεται στην αρχή του δρόμου. Για οποιεσδήποτε δύο διαβάσεις ~A~ και ~B~, θα υπάρχει το πολύ ένας δρόμος από την ~A~ στη ~B~. Μπορείτε να υποθέσετε ότι η επιτάχυνση είναι στιγμιαία και ότι δεν θα σας επηρεάσει η κίνηση. Και φυσικά δεν οδηγείτε ποτέ ταχύτερα από το ισχύον όριο ταχύτητας.

Περιορισμοί

• ~2 \le N \le 150~
• ~0 \le D, A, B < N~
• ~0 \le V \le 500~
• ~0 \le L \le 500~

Είσοδος

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

Κάθε μία από τις ακόλουθες ~M~ γραμμές περιγράφει έναν δρόμο. Κάθε γραμμή αποτελείται από τέσσερις ακέραιους αριθμούς ~A~, ~B~, ~V~ και ~L~, χωρσμένους μεταξύ τους με κενά διαστήματα που δηλώνουν ότι ο δρόμος πηγαίνει από τη διάβαση με επισήμανση ~A~ στη διάβαση ~B~ , έχει όριο ταχύτητας ~V~ και μήκος ~L~. Αν το ~V~ είναι μηδέν, αυτό σημαίνει ότι λείπει η πινακίδα του ορίου ταχύτητας. Ο χρόνος ~T~ που απαιτείται για έναν δεδομένο δρόμο είναι επομένως ~T = \frac{L}{V}~ αν ~V \neq 0~ , διαφορετικά ~T = \frac{L}{V_{old}}~ , όπου ~V_{old}~ είναι το όριο ταχύτητας που τηρούσατε πριν φτάσετε στη διάβαση. Σημειώστε ότι η διαίρεση πρέπει να γίνεται με αριθμούς κινητής υποδιαστολής για να αποφευχθεί η περιττή στρογγυλοποίηση. Στην αρχή βρίσκεστε στη διασταύρωση ~0~ και η τρέχουσα ταχύτητά σας είναι ~70~.

Έξοδος

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

Παράδειγμα

input

6 15 1
0 1 25 68
0 2 30 50
0 5 0 101
1 2 70 77
1 3 35 42
2 0 0 22
2 1 40 86
2 3 0 23
2 4 45 40
3 1 64 14
3 5 0 23
4 1 95 8
5 1 0 84
5 2 90 64
5 3 36 40

output

0 5 2 3 1

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

Ο απαιτούμενος χρόνος σε αυτή την περίπτωση είναι 2,628 μονάδες.