Waterloo Tag

Ο Roger και ο Troy παίζουν κυνηγητό στο Πανεπιστήμιο του Waterloo. Το Πανεπιστήμιο του Waterloo μπορεί να αναπαρασταθεί ως ~N~ κτίρια που συνδέονται με ~M~ πεζοδρόμους. Ο ~i~-οστός πεζόδρομος συνδέει τα κτίρια ~a_i~ και ~b_i~ και έχει μήκος ~d_i~ μέτρα. Υπάρχει το πολύ ένας πεζόδρομος ανάμεσα σε κάθε ζεύγος κτιρίων. Οι πεζόδρομοι δεν τέμνονται (δηλαδή, μπορείτε να μετακινηθείτε από έναν πεζόδρομο σε έναν άλλο μόνο σε κάποιο κτίριο) και ενδέχεται να μην βρίσκονται όλοι στο ίδιο επίπεδο, λόγω γεφυρών και σηράγγων. Ξεκινώντας από οποιοδήποτε κτίριο, είναι δυνατό να φτάσετε σε οποιοδήποτε άλλο κτίριο περπατώντας κατά μήκος των πεζοδρόμων.

Ο Roger ξεκινά το παιχνίδι κυνηγητού από το κτίριο ~1~ και μπορεί να περπατά με ταχύτητα έως και ~v_1~ μέτρα ανά δευτερόλεπτο. Ο Roger μπορεί επίσης να περιμένει σε κάποιο κτίριο ή οπουδήποτε πάνω σε έναν πεζόδρομο. Ο Roger θα κινηθεί με τέτοιον τρόπο ώστε να μεγιστοποιήσει τη διάρκεια του παιχνιδιού.

Ο Troy θα επιλέξει ένα κτίριο ~x~ και θα αφήσει μια ομάδα φοιτητών σε αυτό. Οι φοιτητές θα εξαπλωθούν κατά μήκος όλων των πεζοδρόμων με ταχύτητα ~v_2~ μέτρα ανά δευτερόλεπτο. Το παιχνίδι κυνηγητού τελειώνει όταν οι φοιτητές του Troy φτάσουν στον Roger.

Για κάθε κτίριο ~x~, πόσο θα διαρκέσει το παιχνίδι κυνηγητού;

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τέσσερις ακέραιους αριθμούς ~N~, ~M~, ~v_1~, ~v_2~, χωρισμένους με κενά (~2 \le N \le 2000~, ~N - 1 \le M \le 5000~, ~1 \le v_1, v_2 \le 100~).

Οι επόμενες ~M~ γραμμές θα περιέχουν από τρεις ακέραιους αριθμούς η καθεμία. Η ~i~-οστή γραμμή περιέχει τους αριθμούς ~a_i~, ~b_i~, ~d_i~ (~1 \le a_i < b_i \le N~, ~1 \le d_i \le 10.000~).

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι ~25~ διαθέσιμοι βαθμοί:

Βαθμοί	Περιορισμοί
~3~	~N = 3~, ~M = 2~
~3~	~N = 3~, ~M = 3~
~7~	~v_1 = v_2 = 1~ και όλοι οι πεζόδρομοι έχουν μήκος ~2~ μέτρα (~d_i = 2~).
~7~	~N \le 100~, ~M \le 200~
~5~	Κανένας επιπλέον περιορισμός.

Έξοδος

Να εκτυπώσετε ~N - 1~ γραμμές. Η ~i~-οστή γραμμή πρέπει να περιέχει τη διάρκεια του παιχνιδιού κυνηγητού, σε δευτερόλεπτα, αν ο Troy αφήσει μια ομάδα φοιτητών στο κτίριο ~i + 1~. Πρέπει να εκτυπώσετε τη διάρκεια ως κλάσμα στην απλούστερη μορφή του.

Σημειώστε ότι ένας ακέραιος ~d~ είναι διαιρέτης ενός ακέραιου ~q~ αν η διαίρεση του ~q~ με το ~d~ δεν αφήνει υπόλοιπο. Ένας ακέραιος ~z~ είναι κοινός διαιρέτης των ακεραίων ~x~ και ~y~ αν είναι διαιρέτης και των δύο. Ένα κλάσμα ~x/y~ βρίσκεται στην απλούστερη μορφή του αν ο παρονομαστής του είναι θετικός και οι ~x~ και ~y~ δεν έχουν κοινό διαιρέτη μεγαλύτερο από τη μονάδα.

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

input

3 2 1 10
1 2 135
1 3 15

output

15/1
5/3

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

Για ~x = 2~, ο Roger πρέπει να περπατήσει μέχρι το κτίριο ~3~. Μετά από ~15~ δευτερόλεπτα, οι φοιτητές φτάνουν τον Roger στο κτίριο ~3~ και το παιχνίδι κυνηγητού τελειώνει.

Για ~x = 3~, ο Roger πρέπει να κινηθεί προς το κτίριο ~2~. Μετά από ~5/3~ δευτερόλεπτα, οι φοιτητές φτάνουν τον Roger στον πεζόδρομο ανάμεσα στα κτίρια ~2~ και ~3~. Παρατηρήστε ότι ο Roger περπάτησε ~1.666\ldots~ μέτρα, ενώ οι φοιτητές περπάτησαν ~15 + 1.666\ldots~ μέτρα.

input

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

output

4/1
4/1
5/1

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

Για ~x = 2~, ο Roger πρέπει να περπατήσει μέχρι το κτίριο ~4~.

Για ~x = 3~, ο Roger πρέπει να περπατήσει μέχρι το κτίριο ~4~.

Για ~x = 4~, ο Roger πρέπει να περπατήσει μέχρι το κέντρο του πεζοδρόμου ανάμεσα στα κτίρια ~2~ και ~3~.