Roger và Troy đang chơi trò đuổi bắt tại Đại học Waterloo. Đại học Waterloo có thể được biểu diễn dưới dạng $N$ tòa nhà được kết nối bởi $M$ vỉa hè. Vỉa hè thứ $i$ kết nối tòa nhà $a_i$ và $b_i$, có chiều dài $d_i$ mét. Giữa bất kỳ cặp tòa nhà nào có tối đa 1 vỉa hè. Các vỉa hè không giao nhau (nghĩa là bạn chỉ có thể di chuyển từ vỉa hè này sang vỉa hè khác tại một tòa nhà), và chúng có thể không nằm trên cùng một mặt phẳng (do có cầu và đường hầm). Bắt đầu từ bất kỳ tòa nhà nào, bạn đều có thể đến bất kỳ tòa nhà nào khác bằng cách đi bộ dọc theo các vỉa hè.

Roger bắt đầu trò chơi tại tòa nhà 1 và anh ấy có thể đi bộ với vận tốc lên tới $v_1$ mét/giây. Roger cũng có thể đợi tại một tòa nhà hoặc đợi ở bất kỳ đâu trên vỉa hè. Roger sẽ di chuyển theo cách tối đa hóa thời gian của trò chơi đuổi bắt.

Troy sẽ chọn một tòa nhà $x$ và thả một nhóm sinh viên tại tòa nhà $x$. Các sinh viên sẽ lan tỏa với vận tốc $v_2$ mét/giây dọc theo tất cả các vỉa hè. Trò chơi đuổi bắt kết thúc khi các sinh viên của Troy bắt được Roger.

Với mỗi tòa nhà $x$, trò chơi đuổi bắt sẽ kéo dài bao lâu?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào gồm 4 số nguyên cách nhau bởi dấu cách $N, M, v_1, v_2$ ($2 \le N \le 2\,000$; $N-1 \le M \le 5\,000$; $1 \le v_1, v_2 \le 100$).

$M$ dòng tiếp theo, mỗi dòng chứa 3 số nguyên, trong đó dòng thứ $i$ chứa các số nguyên $a_i, b_i, d_i$ ($1 \le a_i < b_i \le N$; $1 \le d_i \le 10\,000$).

Bảng sau đây cho biết cách phân bổ 25 điểm:

Dữ liệu ra

Xuất ra $N-1$ dòng, trong đó dòng thứ $i$ chứa thời gian của trò chơi đuổi bắt tính bằng giây nếu Troy thả một nhóm sinh viên tại tòa nhà $i+1$. Bạn phải xuất thời gian dưới dạng phân số tối giản.

Lưu ý rằng một số nguyên $d$ là ước của một số nguyên $q$ nếu không có số dư khi $q$ chia cho $d$. Một số nguyên $z$ là ước chung của các số nguyên $x$ và $y$ nếu $z$ là ước của cả $x$ và $y$. Một phân số $x/y$ ở dạng tối giản nếu $y$ dương, và $x$ và $y$ không có ước chung nào lớn hơn 1.

Ví dụ

Ví dụ 1

3 2 1 10
1 2 135
1 3 15

Ví dụ 1

15/1
5/3

Ghi chú 1

Với $x = 2$, Roger nên đi bộ đến tòa nhà 3. Sau 15 giây, các sinh viên bắt được Roger tại tòa nhà 3 và trò chơi kết thúc.

Với $x = 3$, Roger nên đi bộ về phía tòa nhà 2. Sau $5/3$ giây, các sinh viên bắt được Roger trên vỉa hè giữa tòa nhà 2 và 3 và trò chơi kết thúc. Lưu ý rằng Roger đã đi được $1.666\dots$ mét và các sinh viên đã đi được $15 + 1.666\dots$ mét.

Ví dụ 2

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

Ví dụ 2

4/1
4/1
5/1

Ghi chú 2

Với $x = 2$, Roger nên đi bộ đến tòa nhà 4.

Với $x = 3$, Roger nên đi bộ đến tòa nhà 4.

Với $x = 4$, Roger nên đi bộ đến trung tâm của vỉa hè giữa tòa nhà 2 và 3.